TAOCP 5.4.1 Multiway Merging and Replacement Selection: reading guide

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.