10-605 · sorting data that does not fit in memory
Low-Memory Scalable Merge Sort
Merge sort can be implemented with minimal memory at scale: fill
whatever RAM you have, sort that batch, spill it to disk
as a sorted run , and then merge runs F at a time
until only one run remains.
Records N
16 24 24 48 64
Memory B (rows)
2 4 6 8
Merge fan-in F
3 3 4 8
Speed
Stop after
⏮ Rewind
◀ Back
▶ Play
Step ▶
New data
Stage
Ready.
Input file — read once, left to right
Memory — holds B rows, never more
Runs on disk
Reading the picture
What to notice. Memory never holds more than B
rows plus one head per open run — the sort is bounded by F, not by
N. Every record crosses the disk boundary twice per pass, so the
whole cost is 2N × (1 + ⌈logF (N/B)⌉)
record-moves: raising F removes entire passes over the data. Note
that sort_fanin=⌈√runs⌉ will lead to a single merge
pass. The one thing a bigger F costs is open file descriptors.
Stability. Ties always resolve to the earliest
run, and sorted() inside a batch is stable — so equal
keys come out in input order, which is what lets a merge join and a
group-by trust the order downstream.
Keys: space play/pause · → step · ← back · home rewind. With stop at every stage boundary checked, Play halts once the spill phase finishes and again after each complete merge pass — one press of Play per stage.