Sorting more than fits
A Socratic walk-through of sorting more than fits — reasoned out one step at a time, not lectured.
The question we started with
THE QUESTION #How do you put a file in order when you cannot hold even a tenth of it at once?
Every sorting method you were taught assumes it can touch any element whenever it likes. Quicksort swaps distant pairs; heapsort walks up and down a tree; even mergesort reads two arms at once. Each assumes the data is there.
Now suppose the file is a terabyte and the machine has eight gigabytes. Ninety-nine per cent of the data is somewhere you cannot reach without asking a disk. What has to change — and is it the algorithm, or something more basic than that?
Reasoning it through
REASONING #Start with the cost model, because that is what actually breaks. In memory, we count comparisons, since every comparison costs roughly the same. Is that still the right unit here? Two elements a terabyte apart are not the same price as two adjacent ones. Reading a contiguous megabyte from a spinning disk costs about what reading a single byte costs, because the expensive part was arriving at the right place at all.
So the currency changes. Stop counting comparisons and start counting block transfers — how many times a chunk of data crosses between disk and memory. Once you accept that unit, the design almost writes itself, because the goal becomes: touch every byte as few times as possible, and touch it sequentially.
How few times could we hope for? At the very least we must read the whole file and write the whole file, so one pass in each direction is the floor. Can one pass do it? Not in general — an element near the end may belong at the front, and you cannot know that without having seen it. So the real question is: how few passes?
Here is the standard two-phase answer. Phase one: read as much as fits — eight gigabytes — sort it in memory with any ordinary method, and write it back out as a sorted run. Repeat until the input is consumed. A terabyte gives 125 runs, each sorted internally, and the whole phase cost one read and one write of everything.
Phase two: merge those runs. Not two at a time, which would need seven passes, but all 125 at once. Keep one small buffer per run in memory, plus a heap of 125 candidates; repeatedly take the smallest, write it to the output, and when a buffer empties, refill it with the next block from that run. Every run is read strictly forwards, so every read is sequential. That is a second read and a second write of the whole file.
Total: four terabytes of transfer to sort one, in two passes. Now check whether the fan-in of 125 was the lucky part or the general case. What limits it? Memory divided by the buffer size — eight gigabytes across 126 buffers is 64 megabytes each, comfortably large. So we could have merged far more runs than we had. This is the crucial asymmetry: the number of passes is roughly the logarithm of the run count in base fan-in, and the base is in the hundreds or thousands. A logarithm in base 1,000 is essentially never larger than two. Files of almost any size sort in two or three passes.
The formal version is the external-memory bound of Aggarwal and Vitter from 1988: sorting N records with memory M and block size B costs on the order of (N/B) times the logarithm of (N/B) in base (M/B) block transfers, and this is optimal. It has the same shape as the comparison bound but every quantity is divided by the block size — which is precisely the statement that blocks, not records, are what you pay for.
And what if you shrink the buffers to raise the fan-in? You get fewer passes in theory and worse performance in practice, because once a buffer is smaller than the disk's efficient transfer size, each refill becomes a seek. That tension — fan-in against buffer size — is the whole tuning problem, and it is why the number that matters is memory divided by block size rather than memory divided by record size.
One classical refinement, often misremembered: replacement selection generates runs longer than memory. Keep a heap of M records, emit the smallest still at or above the last value emitted, and hold anything below that watermark for the next run. On randomly ordered input the runs average about twice memory, by Knuth's analysis — halving the run count, though at so large a logarithmic base that this rarely removes a whole pass.
The analogy
THE ANALOGY #Think of alphabetising a library's worth of index cards on a small desk. You cannot spread them all out. So you take a deskful, sort it by hand, band it and set it on a shelf, and repeat until the boxes are empty. Then you lay one banded stack in front of you at a time — forty of them, each open at its first card — and repeatedly take whichever visible card comes first alphabetically. You never look deeper than the top card of any stack, so the desk holds forty cards, not forty thousand.
the desk analogy makes the constraint feel like space, when the real constraint is the cost of fetching — the cards are all equally close to hand, whereas the whole design exists because reaching for a distant block costs thousands of times what reaching for the next one does.
Clarifying the model
THE MODEL #Two refinements.
First, the algorithm did not really change. Phase one uses an ordinary in-memory sort and phase two is exactly mergesort — only merging 125 ways instead of two. What changed was the accounting, and the accounting then dictated the shape. This is the general lesson of the memory hierarchy: an algorithm is only optimal relative to a cost model, and swapping the model can make a textbook winner a poor choice without a single line of it being wrong.
Second, the pass count is a step function, which matters more than any constant factor. Going from two passes to three is a fifty per cent increase in I/O, and it happens abruptly when the run count exceeds the fan-in. So the practical objective is to stay on the right side of that step — usually by giving the sort more memory, since memory raises the run length and the fan-in together.
A picture of it
THE PICTURE #How to readthe upper loop is phase one — it cycles once per run and ends when the input is exhausted. The self-transition on the merge state is phase two, executed once per output record. Every arrow crossing between disk states is a sequential pass over the whole file, and there are only four of them.
What became clearer
WHAT CLEARED #Sorting more than fits is not a different algorithm but a different unit of cost. Count block transfers instead of comparisons and mergesort reappears, reshaped: sort what fits, then merge hundreds of runs at once so that the logarithm has an enormous base and the pass count collapses to two. The constraint was never really the memory — it was the price of arriving somewhere on the disk.
Where to go next
ONWARD #- Cache-oblivious algorithms, which achieve the same optimal transfer counts without being told the block or memory size.
- How a database query planner decides between an external sort and a hash-based aggregation for the same grouping query.
- Distributed sorting, where the network takes the disk's role and the same pass-counting reasoning reappears at a different scale.
Key terms
TERMS #| Term | What it means |
|---|---|
| Run | a contiguous, internally sorted stretch of records written out during the first phase. |
| Fan-in | how many runs a single merge pass consumes at once; set by available memory divided by the per-run buffer size. |
| Block transfer | one contiguous read or write between disk and memory; the unit of cost in external-memory analysis. |
| Replacement selection | a run-generation technique using a heap and a watermark, producing runs about twice the size of memory on random input. |
Every term the collection defines is gathered in the glossary.