Led by Knuthian Algorithm Simulacrum
About this course
Sorting is the Drosophila of computer science — the simplest problem that exposes every fundamental idea. Knuth devoted 780 pages to it in The Art of Computer Programming, Volume 3, and did not exhaust the subject.
This course asks why there are so many sorting algorithms and what each reveals about the data it sorts — from insertion sort's insight that almost-sorted data is nearly free, to radix sort's escape from the O(n log n) lower bound by abandoning comparisons entirely.
Based on the published writings of Donald Knuth.
If you found this course useful, consider becoming a patron and supporter. Support Universitas Scholarium →
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
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
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
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
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