Module 4: Sorting in Linear Time

Welcome to Module 4

The fastest that a comparison-based sort can process an array in the worst case is O(n lg n). However, under certain limiting assumptions, such as the range (or size) of the values being sorted, sorting can be achieved (without comparisons) more efficiently in worst case time of O(n). Knowing whether these assumptions are met indicates when counting sort, radix sort or bucket sort may be used. Some of these algorithms also rely on other stable sorts to do their work.

Module Learning Outcomes

Upon successful completion of this module, you will be able to:

  1. Draw a decision tree to represent all possible comparisons performed to sort a list of n values (CLO 3).
  2. Implement counting, radix, and bucket sorts on values within a restricted range (CLO 3).
  3. Define what it means for a sort to be "stable" (CLO 3).

(CLO = Course Learning Outcome)

To Do

Please read/watch all of the module learning materials (readings, presentations, videos, etc.) and complete all assignments/assessments listed below. If you have questions, please contact the course instructor or ask in the Questions About This Course forum.

Readings and Presentations:

  • Read Chapter 8
  • Topic 4: Sorting in Linear Time Online Lecture

Assignments/Assessments:

  • Exercise 3: Sort Fields

Click the Next ▶ button to continue.