02 / A textbook algorithm, measured2026
Sorts files far larger than its memory budget, with two run-generation algorithms behind one shared I/O layer so they can be benchmarked against each other.
20:1
data to memory
2.9x
slower at its best
47
tests
Author
my role
Knuth's replacement selection generates sorted runs averaging twice the memory budget, so there are half as many runs left to merge. Databases relied on it for decades. PostgreSQL deleted it in 2017 and the commit message blamed advances in CPU technology without showing any numbers. This builds both algorithms behind a shared I/O layer, memory budget and merger, so run generation is the only variable between them, and then measures the difference.
What I did
- 01Implemented replacement selection as a min-heap and a parked region living inside one pre-allocated buffer, so deferring a record to the next run costs no extra memory and the two regions cannot collide.
- 02Confirmed the theory holds and loses anyway: it hits the predicted run length and moves a third of the bytes, yet is 2.9x slower even in its best case, because an NVMe drive returns a block faster than the interpreter sifts a heap three million times.
- 03Derived the break-even point analytically and confirmed it by simulating per-I/O latency, showing the textbook algorithm only wins above roughly 0.5 ms per operation, about where storage sat before flash.
- 04Wrote tests that assert the finding rather than the implementation, so CI re-derives the run counts, merge depth and I/O amplification on hardware I do not own.