TAOCP Vol 3: Sorting and Searching · Week 82
TAOCP 5.3.1 Minimum-Comparison Sorting: reading guide
How few comparisons can sort n items? The information-theoretic lower bound of about lg n!, and merge insertion (Ford-Johnson), which comes remarkably close for small n.
Time About 8 hours this week
Why it matters
The lower bound is the reason no comparison sort beats O(n log n). This section also teaches how to think about decision trees, a general lower-bound tool.
Before you start
- 1.2.5 Factorials
- 5.2 Internal Sorting
How to approach it
Draw the decision tree for sorting 3 elements. Try to find a 7-comparison sort for 5 elements on your own before reading how. Read merge insertion with pencil.
Exercises
Do every exercise rated 00 to 20 in your head or on paper; they are quick and they check you actually absorbed the definitions. Then pick two or three rated 20 to 25 (M or not) and grind them out fully. Attempt one M25 to M30 and give yourself a hard 90-minute cap before reading the answer. Always read the answer to every exercise you attempted, even the ones you got, because Knuth's answers often teach a second technique.
Traps
- Confusing worst-case comparisons with average-case.