In external merge sort, why does the pass count decide runtime rather than the comparison count?

## Two cost models, and why the usual one is the wrong one The habitual model for sorting counts comparisons, and it says every comparison sort is Ω(n log n) and the good ones are Θ(n log n). That model is fine when the data is in memory, because a comparison and a data access cost about the same. External sorting breaks the assumption: a comparison costs on the order of a nanosecond, while pulling a block off durable storage costs microseconds to milliseconds. When one operation is thousands to millions of times more expensive than the other, an accounting that counts the cheap one is not a model — it is noise. The replacement model counts **passes**. One pass reads every byte once and writes every byte once, so a pass over `N` bytes moves `2N`. For a 500 GB clickstream archive that is roughly 1 TB per pass. A two-pass sort moves about 2 TB; a three-pass sort moves about 3 TB. Both do Θ(n log n) comparisons. One is fifty percent slower. This is exactly the situation the wrong answer misses: *"big-O says n log n either way, so the pass count is a detail."* The pass count is not a detail; it is the answer. ## Why the comparisons genuinely disappear It is worth being precise about why the CPU side can be ignored rather than merely asserted. During a merge the process is doing two things concurrently: comparing the current heads of the open runs, and waiting for storage. With double buffering — while block `k` of a run is being merged, block `k+1` is already in flight — the comparison work runs inside the I/O wait. The merge then proceeds at device bandwidth, and the CPU has slack. Make the comparator twice as fast and nothing changes; the job still waits on storage. Remove one pass and a third of the elapsed time disappears. The practical corollary is that optimisation effort in an external sort should be aimed at exactly two quantities: - **The pass count** — the integer number of times the data crosses the boundary. - **The bytes moved per pass** — reduce the records themselves and every pass gets cheaper: compress runs, project away columns nobody needs downstream, or sort a compact `(key, record-pointer)` pair instead of whole records when the payload is large. Anything else — a faster in-memory sort in phase one, a cheaper comparator, more threads on comparisons — is optimising the resource that is already idle. ## The step function Because passes are integers, the payoff curve is a staircase, not a slope. Suppose the run count sits at 1000 and the fan-in at 127: two merge passes, three total. Nudging fan-in to 200 changes nothing — still two merge passes, since 1000 is still above 200. Getting fan-in to 1000 collapses the merge to one pass and removes a third of the total I/O in one step. So the useful question about any proposed tuning is not "does this improve a metric?" but "does this cross a boundary?" — the run count passing under the fan-in, or under fan-in squared. Improvements that do not cross a boundary buy nothing measurable. ## The tension nobody states until you are senior With fixed sort memory `M` and buffer size `b`, the fan-in is `F = M/b - 1`. Fan-in and buffer size trade directly against each other, and both matter: - **Shrink `b`** and `F` rises, which lowers the pass count. But each read of each stream becomes small. With many streams active, the device sees interleaved small requests across `F` different regions — the request pattern drifts from sequential toward scattered, per-request latency stops being amortised over a big transfer, and effective bandwidth collapses. You can win the pass count and lose more than you won. - **Grow `b`** and each stream is read in long sequential chunks at full bandwidth. But `F` falls, and if it falls below the run count you buy an entire extra pass. The rule that follows is an ordering, not a formula: first find the smallest fan-in that achieves your target pass count, then spend every remaining byte of memory on making the buffers as large as possible. Maximising fan-in for its own sake is a classic self-inflicted wound — the job hits its two-pass target and still runs at a quarter of device bandwidth because each of a thousand streams is being read 64 KB at a time. ## Diagnosing the gap This gives a concrete diagnostic when an external sort runs far slower than `passes × 2N / bandwidth` predicts. Compare achieved throughput against the device's sequential ceiling. If the job is at a small fraction of it, the merge is not streaming: check whether fan-in was pushed so high that per-stream buffers went tiny, whether read-ahead is actually happening or every block is fetched on demand with the CPU idle in between, and whether the runs and the output share a device that is now servicing reads and writes by turns. If throughput is near the ceiling and the job is still too slow, the pass count or the bytes per pass is the only thing left to attack — and at that point more memory, fewer columns, or compressed runs are the real levers.