Walkthrough — Module 15: External Sorting

Read this AFTER a stage is green — it explains how the reference solution is built and why.

Stage 1: Replacement selection: runs twice the memory

The reference collapses Knuth's five steps R1–R5 onto a BinaryHeap<Reverse<(usize, i64)>>, and the choice of key (run number, key) is what makes the algorithm fall out almost for free: popping the heap always yields the smallest key of the lowest live run number, which is exactly "output the top" (R3), and the run-number tag is the frozen/not-frozen distinction (R5). The end-of-run test (R2) is a single comparison if rn != current_rn — when the popped record's run number has advanced, every remaining record is frozen, so the current run closes and the next begins. There is no explicit "is memory all frozen?" scan; the ordering does it.

The subtlety the design gets right is the freeze decision: a newly read x joins run rn+1 iff x < key, where key is the record just output (LASTKEY). Comparing against the just-output key, not against some running maximum, is what implements "cannot extend the current run." The snow-plow consequences are visible in the reference tests: sorted input yields a single run (the plow never meets snow behind it), reverse-sorted yields runs of exactly P (every arrival freezes), and random input yields average length ≈ 2P. A degenerate p = 1 reduces to the input's natural ascending runs — a good sanity check that the heap machinery didn't introduce spurious breaks.

Stage 2: k-way merging with a tree of losers

LoserTree is the reason this module can claim the information-theoretic comparison rate. The array layout — kk = k.next_power_of_two(), internal nodes at 1..kk, leaf j at conceptual slot kk + j, parent i/2 — puts every leaf at depth exactly ⌈lg k⌉, so a replay is a fixed-length climb. The decisive idea is stored state: loser[node] holds the loser of the match previously played at node, and when a new champion candidate climbs from a leaf it meets, at each level, only that stored loser (in pop's while node >= 1 loop). A winner tree would have to re-read both children at every node; the loser tree already has the sole relevant opponent waiting, halving the comparisons.

Two idioms are worth stealing. First, +∞ is modeled as None via key(), and beats() handles the three cases (None loses, Some beats None, Some vs Some compares) so exhausted runs need no special-casing anywhere else — end-of-run is just a leaf that always loses. Second, the comparison counter is incremented only in the Some(x), Some(y) arm, so it counts genuine key–key comparisons and not the free +∞ flag checks; this is what lets the tests assert the exact n·⌈lg k⌉ + k bound. new plays the initial tournament bottom-up with a single recursive play(1) that both fills every loser[node] and returns the champion into loser[0], so the structure is fully primed before the first pop.

Stage 3: Polyphase merge: Fibonacci on tape

polyphase_distribution climbs the generalized-Fibonacci levels from (1, 0, ..., 0) until the perfect total covers num_runs, and returns that whole level. The recurrence a1' = a1+a2, ..., a_{T-2}' = a1+a_{T-1}, a_{T-1}' = a1 is the multi-tape Fibonacci that guarantees the merge stays "perfect" — exactly one tape empties per phase. The reference's cleanest decision is the dummy-run convention: rather than special-casing non-Fibonacci run counts, it rounds up to the next perfect level and lets polyphase_core materialize the shortfall as empty Vecs. Dummies participate in merges at zero record cost, so the phase structure is uniform whether or not the run count is a perfect Fibonacci number.

polyphase_core is the shared engine (also used by stage 4), and its loop encodes the polyphase invariant directly: it finds the one empty tape as this phase's output, computes m = the minimum run count among input tapes, performs m (T-1)-way merges (each popping one run from every input tape and merging via the stage-2 merge_runs), then loops. When <= 1 run remains total it returns the survivor and the phase count. Because it takes &mut IoStats, the same routine can be run "for free" by stage 3 (polyphase_merge passes a throwaway accountant) or billed by stage 4. Threading a shared supply iterator through the distribution, with supply.next().unwrap_or_default() supplying an empty run when the real runs run out, is the neat trick that turns "top up with dummies" into two words of code — and a debug_assert!(supply.next().is_none()) guards against a distribution that is too small.

Stage 4: The full pipeline, with I/O accounted

external_sort is intentionally thin: it charges run formation as one full pass (records_read += n, records_written += n) and then delegates the merge phases to polyphase_core with a shared &mut io, so every merge's reads (sum of input-run lengths) and writes (merged length) accrue to the same accountant. Keeping all merge accounting inside polyphase_core rather than duplicating it here is why the two stages never disagree about the bill. The result is that records_written <= n·(1 + phases) holds by construction, and the model is honest: comparisons are treated as free, record transfers as the whole cost, exactly as §5.4 argues for real tape/disk sorting.

The boundary case is the tell-tale that the accounting is right: an input that replacement selection swallows into a single run — already sorted, or memory >= n — produces zero merge phases, so records_read == records_written == n, one pass and no merging (the reference test asserts exactly 5000/5000 on a sorted 5000-element input). This is the payoff of composing the three stages: the pipeline's I/O bill is a direct, checkable function of how many runs stage 1 produced and how many phases stage 3's Fibonacci level implies, and examples/bench.rs traces that curve at growing n so you can see the pass count creep up like the logarithm of the run count.