COMP 1101 · The Art of Sorting

Led by Knuthian Algorithm Simulacrum

Why are there so many sorting algorithms? Each embodies a worldview. Based on the published writings of Donald Knuth.

1. Module 1

   Why Sorting Matters

   Led by Knuthian Algorithm Simulacrum

   The question

   Each sorting algorithm embodies a different worldview about data structure. Before you can choose between algorithms, you need to understand the worldview. What are the three performance dimensions of a sorting algorithm — and why does stability matter?

   Outcome

   The student can define sorting, explain the three performance measures, and distinguish comparison from non-comparison sorts.

   Sub-units

   1. ○ 1.1 What Is Sorting? Open this unit → ✓ ↻
   2. ○ 1.2 Performance Measures Open this unit → ✓ ↻
   Begin the course → Print certificate of completion
2. Module 2

   Simple Sorts: Insertion, Selection, Bubble

   Led by Knuthian Algorithm Simulacrum

   The question

   O(n²) sorts are slow — but insertion sort is optimal for nearly-sorted data. When does slowness in the worst case coexist with optimality in the real case?

   Outcome

   The student can implement insertion sort and state when O(n²) sorts outperform faster alternatives.

   Sub-units

   1. ○ 2.1 Implement Insertion Sort Open this unit → ✓ ↻
   2. ○ 2.2 When Is Slow Fast? Open this unit → ✓ ↻
   Open this module → Print certificate of completion
3. Module 3

   Divide and Conquer: Mergesort and Quicksort

   Led by Knuthian Algorithm Simulacrum

   The question

   Mergesort guarantees O(n log n). Quicksort expects O(n log n) but can hit O(n²). Why does the worse algorithm often run faster in practice — and what is the O(n log n) lower bound?

   Outcome

   The student can implement mergesort, explain quicksort's pivot problem, and state the O(n log n) lower bound.

   Sub-units

   1. ○ 3.1 Mergesort Open this unit → ✓ ↻
   2. ○ 3.2 Quicksort and the Pivot Open this unit → ✓ ↻
   3. ○ 3.3 Essay: The Lower Bound Open this unit → ✓ ↻
   Open this module → Print certificate of completion
4. Module 4

   Beyond Comparisons: Radix and Counting Sort

   Led by Knuthian Algorithm Simulacrum

   The question

   The O(n log n) lower bound applies only if you use comparisons. Radix sort and counting sort use structural knowledge about the data instead — and run in O(n). Is this cheating, or a deeper insight about the relationship between algorithms and data models?

   Outcome

   The student can implement counting sort and explain when non-comparison sorts apply.

   Sub-units

   1. ○ 4.1 Counting Sort Open this unit → ✓ ↻
   Open this module → Print certificate of completion
5. Module 5

   Choosing the Right Algorithm

   Led by Knuthian Algorithm Simulacrum

   The question

   There is no universally best sorting algorithm. The correct question is not "which is fastest?" but "what do I know about my data?" Given five specific datasets, which algorithm is best for each — and why?

   Outcome

   The student can choose the appropriate algorithm for a given dataset and articulate two algorithms as worldviews.

   Sub-units

   1. ○ 5.1 The Tournament of Sorts Open this unit → ✓ ↻
   2. ○ 5.2 Final Essay: Sorting as Worldview Open this unit → ✓ ↻
   Open this module → Print certificate of completion