Week 85 of 125
TAOCP 5.4.1 Multiway Merging and Replacement Selection
Sign up or sign in to tick these off and give this week a due date.
-
Merging many sorted runs at once using a tree of losers, and replacement selection, which produces initial sorted runs about twice the size of memory on random data (the snowplow argument).
Time About 8 hours this week
Why it matters
This is still exactly how external sorts and database sort operators work when data does not fit in RAM. Probably the most practical section of 5.4.
Before you start
- 5.2.3 Sorting by Selection (heaps)
How to approach it
Implement replacement selection with a heap and measure run lengths on random data; you should see about 2P. Implement a k-way merge with a heap. Read the snowplow analogy carefully; it is a lovely argument.
Exercises
Work every exercise rated 10 to 20; most are about tracing the algorithm by hand or tweaking one step, which is exactly the skill you want. Pick one or two rated 20 to 25 that involve modifying the algorithm and implement your modification in a real language with tests. Skip HM exercises unless you enjoy calculus, and treat anything rated 40+ as a research problem, not homework.
Traps
- Forgetting to mark records that belong to the next run in replacement selection.