External Sorting: Run Generation, k-Way Merge, and the Fan-In Limit

Sorting a terabyte on a machine with a few gigabytes of memory removes the assumption that every element can be touched at random. Once the input exceeds memory, the cost model changes: the number of passes over the data, and the number of seeks between them, dominate everything that comparison counts measure. External sorting is the set of techniques that minimise passes, and each of them is a concession to a specific hardware constraint.

The cost model that replaces comparisons

Internal sorting counts comparisons because comparisons are the operation that scales with $\log n$. For data on a block device, the operation that scales is the transfer. Two numbers matter:

• Sequential bandwidth. Reading a contiguous region costs a fixed per-block cost plus a per-byte cost. Large reads amortise the fixed part.
• Seek or random-access latency. Moving the head, or issuing a random read on a solid-state device, costs orders of magnitude more than transferring the block that is eventually read.

The ratio between seek latency and the time to transfer a block is what makes external sorting a different problem. On a rotating disk the ratio is large enough that a merge pass which reads $k$ runs sequentially is fine, while one that interleaves reads from $k$ runs at random offsets is not. On solid-state storage the ratio is far smaller, which raises the optimal fan-in, but the same structure applies.

The quantity to minimise is the number of times the whole dataset is written and read. A sort that produces sorted runs in one pass and merges them in $p$ passes writes the dataset once per pass and writes the final output once, so the total is $p+1$ passes over the data, plus the initial read. Reducing $p$ by one is worth more than any constant-factor improvement in the merge’s inner loop.

Run generation with a bounded buffer

The first phase turns the input into sorted runs, each small enough to fit in memory. The naive approach loads a buffer, sorts it internally, writes it out, and repeats, producing runs of exactly the buffer size. With a buffer of $B$ elements and $N$ total, that is $N/B$ runs, and the merge phase must then handle that many.

Replacement selection produces runs longer than the buffer, on average about twice as long, by treating the buffer as a heap and streaming the input through it. The invariant is a heap of $B$ elements representing the current run’s candidates. Repeatedly extract the minimum and write it to the run, then read the next input element. If it is at least the last element written, it belongs to the current run and goes into the heap. If it is smaller, it cannot belong to the current run, so it is held aside for the next run.

The heap therefore shrinks as elements are deferred, and the current run ends when the heap is empty of current-run candidates. The deferred elements then form the initial heap for the next run.

/* sketch: one replacement-selection run from a stream */
while (heap_size > 0) {
    x = heap_pop_min();
    emit(x);
    if (next_input(&y)) {
        if (y >= x) heap_push(y);        /* eligible for this run: replaces x */
        else        defer(y);            /* needs a later run: held aside */
    }
    /* a deferred element must be re-admitted once the count emitted in this
       run has advanced far enough; the sketch omits that bookkeeping */
}
/* deferred elements seed the next run's heap */

The count of deferred elements matters. A deferred element is smaller than the last key emitted, so it cannot enter the current run immediately; the standard implementation records, for each deferred element, how many further emissions must happen before the run’s output passes its key, and re-admits it when that count reaches zero. The run therefore ends when the heap has no candidate left and no deferral is due within the run.

The run length depends on the input’s existing order. For random input, the expected run length is approximately $2B$: on average half of the heap’s contents have been deferred by the time the current run ends. For input that is already sorted, every new element is at least the last emitted, so nothing is deferred and the entire input becomes one run. For reverse-sorted input, every new element is smaller than the last emitted, so each replaces a deferred element one for one, the heap never shrinks, and runs are exactly $B$ long, the worst case.

The gain is a factor of about two in run count on random input, which is one fewer merge pass whenever the run count crosses a power of the fan-in. That is the entire reason the technique exists, and it costs nothing beyond the heap bookkeeping.

The k-way merge and the loser tree

The merge phase takes $k$ sorted runs and produces one, reading the current front element of each run and emitting the smallest. A naive implementation scans all $k$ fronts to find the minimum, costing $k-1$ comparisons per output element, so the whole merge costs $(k-1)N$ comparisons. With $k = 64$ that is 63 comparisons per element, more than the $\lceil \log_2 N \rceil$ levels the internal sort needs for typical $N$.

A tournament tree reduces this to $\log_2 k$ comparisons per element. Leaves hold the $k$ run indices; each internal node holds the index of whichever of its two children currently has the smaller front key; the root therefore holds the run whose front is the global minimum. Consuming that element and advancing its run invalidates only the nodes on the path from that leaf to the root, so a replay of $\lceil \log_2 k \rceil$ comparisons restores the invariant.

/* tree[1..2k-1]; leaves at [k, 2k) hold run indices, tree[1] holds the winner */
static void replay(int *tree, int k, int leaf)
{
    for (int i = (leaf + k) / 2; i >= 1; i /= 2) {
        int l = tree[2 * i], r = tree[2 * i + 1];
        tree[i] = (front_key(l) <= front_key(r)) ? l : r;   /* exhausted run = +inf */
    }
}

The loser-tree variant stores the loser at each internal node rather than the winner, and keeps the current winner in a separate variable. On the replay path from the leaf that just advanced, every node on the path records the loser of its match, so the winner needs no extra write at the root: the replay still walks the same height. It is the form given in the classic treatments of external merge, and its saving is that the root node disappears, which costs no extra storage and clarifies the update.

The tree holds indices into the run buffers, so the comparison reads the front element of each run’s buffer, not the run on disk. The buffers must be large enough that reading one block serves many outputs; a buffer of one block per run is the minimum, and larger buffers amortise the read latency across more emissions.

The fan-in limit

The fan-in is bounded in both directions. It is limited from above by memory: each run needs a read buffer, and the output needs a write buffer. With a memory budget of $M$ bytes, block size $b$, and one block per buffer, the maximum fan-in is roughly $M/(2b)$.

It is limited from below by the pass count. With $R$ initial runs and fan-in $k$, the number of merge passes is $\lceil \log_k R \rceil$. Larger $k$ means fewer passes, so memory should be spent on width until the pass count reaches one or two.

The reason not to push $k$ higher is that beyond a point the merge becomes seek-bound rather than bandwidth-bound. If each run is on a different region of the device and the read buffer is one block, the merge performs a seek per block per run, and the seek time dominates. The classic remedy is to read a large chunk from each run and to arrange the merge so that reads are grouped: refill each run’s buffer fully before returning to it, and stagger the refills so the device sees long sequential reads.

A second constraint is the number of simultaneously open files or streams. Operating systems impose per-process limits on open descriptors, and a fan-in above that limit requires either multiple passes with narrower merges or an abstraction that multiplexes several runs over one file by seeking. The descriptor limit is a hard ceiling that appears in real external sort implementations as a configurable maximum merge width.

Two passes as the target

With replacement selection producing runs of about $2B$ and a memory budget that allows a fan-in of $k$, the number of merge passes is about $\lceil \log_k (N/2B) \rceil$. A dataset a hundred times the size of the buffer, so that $N/2B = 50$, needs only one merge pass at $k = 64$, and datasets up to fifty times the size of memory have the same property. That is the design target: one run-generation pass and one merge pass, plus the initial read and the final write.

Two refinements push further. If the fan-in is not sufficient for a single merge pass, a cascaded merge can combine the final merge with the output stage, or the run generation can produce fewer, longer runs by using a larger buffer. Both reduce transfers at the cost of memory or complexity.

The opposite refinement is distribution: instead of one merge, partition the data by key range into buckets that each fit in memory, then sort each bucket independently. This is a distribution sort in the sense of counting and radix sorting, applied at the granularity of disk blocks, and it trades merge passes for a partitioning pass plus a requirement that the key distribution be known well enough to choose range boundaries.

Where external sorting fails

The techniques above assume the input is a file that can be read more than once and that runs can be stored somewhere. Neither is guaranteed. A stream that arrives once and cannot be rewound must be sorted by a different means: partition into memory-sized chunks and merge as the chunks arrive, which is the same algorithm but with the input read only once and the merge interleaved with generation.

A second failure mode is a key distribution that makes run generation useless. If the input arrives in an order that is random with respect to the sort key but has strong local structure in another field, the runs are the expected $2B$; if it arrives in an order that is anti-correlated with the key, every element is deferred and the runs are exactly $B$. The algorithm degrades gracefully to the naive case and no worse, but the factor-of-two expectation should not be relied on for adversarial or unusual inputs.

The third is the cost of the comparison itself. External sorts compare keys that may be long strings or composite records, and the comparison happens once per element per merge pass, inside a tree replay. Extracting a fixed-width sort key into a parallel array, sorting by key and permuting records at the end, converts a variable-length comparison into an integer comparison and usually pays for the extra pass. The same reasoning that motivates comparator discipline in memory applies with more force here, because the comparison is repeated once per pass.