Sorting what will not fit

Ten sorting algorithms have been measured on this site and every one of them assumed the array was in memory. That assumption is not a detail of the implementation. It is what makes a.get(i) cost one, and without it none of the ten has a stated cost at all.

A file that does not fit is sorted by a different algorithm, and it is not a modification of any of the ten. It is external merge sort, it has been the answer since the tape era, and its shape is dictated entirely by two numbers that no comparison count contains.

Two phases, and only the second one has a class #

The algorithm is two phases and both are ordinary.

Run formation. Read M elements — as many as fit — sort them by any in-memory method, write them back. Repeat until the file is a sequence of ⌈n/M⌉ sorted runs. This phase reads the file once and writes it once: 2n/B transfers, and no choice made here changes that number.

Merging. Take k runs at a time, keep one block of each in memory plus one block for the output, and repeatedly emit the smallest head. Each such pass reduces the number of runs by a factor of k and reads and writes the whole file: another 2n/B transfers. Repeat until one run remains.

The total is therefore 2(n/B)(1 + ⌈log_k(n/M)⌉) transfers, and the whole question is what k can be.

k is M/B − 1. One block of memory per input run, and one for the output. That is the entire derivation and it is the sentence that carries the field: the fan-in is not a tuning parameter, it is how many blocks fit in memory, less one. Everything else about the algorithm’s cost follows from it.

Which gives the class:

$$\Theta\!\left(\frac{n}{B}\,\log_{M/B}\frac{n}{B}\right)$$

and every term in it is a quantity that a comparison count cannot see.

The base of the logarithm is the whole story #

An in-memory merge sort has a base-2 logarithm because a merge takes two runs. There is no reason for that other than convenience: with the whole array addressable, merging 32 runs at once is possible and pointless, since the work is the same and the bookkeeping is worse.

In external memory the base is M/B, and M/B is enormous. With a 16-kilobyte block and a gigabyte of memory, M/B is 65,536, so log_{M/B} of anything a real system holds is one or two. Not “logarithmic” in any practical sense — one or two.

That is why external sorting is usually described as a two-pass algorithm rather than as an n log n one. A file of a terabyte, sorted with a gigabyte of memory: run formation gives a thousand runs of a gigabyte each, and 65,536 runs can be merged at once, so one merge pass finishes it. The logarithm is 1, and the cost is 4n/B — read, write, read, write.

The measured version of that arithmetic is the figure below, and it is not a curve.

Why a staircase and not a slope #

Everything in this field is a ceiling of a logarithm, and a ceiling is a staircase.

The number of passes is ⌈log_k(runs)⌉, which changes only when the number of runs crosses a power of the fan-in. Between those crossings, more memory changes the fan-in, changes the number of runs, and changes nothing at all about the number of passes — which is the only quantity the cost depends on.

This has a consequence that anybody who has operated a database has met without necessarily having a name for it. A sort with just enough memory is fast; a sort with slightly too little is a third slower, not slightly slower; and the boundary is sharp, invisible in any monitoring that reports memory as a percentage, and lands in a different place for every file size.

It is also the sharpest case this site has yet found of a distinction it has made since the foundation. A complexity class is a statement about a limit, and an operational cost is a statement about a threshold. The class here is genuinely (n/B)log_{M/B}(n/B) and genuinely correct. The behaviour anybody experiences is a step function, and reading the first as a description of the second is exactly the error a limit is not a prediction is about — arriving here with a much sharper edge, because the steps are a third of the cost rather than a constant factor.

The measurement, and what it caught #

Every point in the opening figure is a real sort. lib/external.js implements run formation and multi-way merging against a BlockIO, the transfers are charged as the elements are consumed, and the output is checked to be sorted before any of it is drawn — the same sortedness check that has caught more mistakes on this site than everything else combined.

Beside the measurement sits the prediction the algorithm’s own pass structure implies: 2(n/B)(1 + passes). The figure asserts that the two agree to within 35%, and at every size drawn they agree to within a few per cent. At n = 4,096, B = 32, M = 256 the measured cost is 768 transfers and the predicted cost is 768 — exactly, because at these sizes every pass really does read and write the whole file with no partial block at either end.

That agreement is worth stating as a check rather than as a result. A measurement that matches its own model has not confirmed the model; it has confirmed that the implementation is the algorithm the model describes, which is a smaller claim and the one that was actually at risk. The site has been caught by the difference before: the practice phase’s withRuns generated inputs whose cost barely moved with the number of runs, and the fit refused a shape that had no business being refused. The refusal was right and the input generator was wrong.

Where the model and the measurement would disagree — and this is the honest part — is at sizes where the partial blocks matter. A merge of seven runs whose lengths are not multiples of B pays for a partial block at the end of each, and the ratio drifts above 1. That is a constant-factor effect, it is visible in the ratios at the smallest sizes drawn, and it is exactly the kind of thing the asymptotic form discards and a measurement does not.

The fan-in that a real system uses is not M/B #

The derivation says the fan-in is M/B − 1 and every real system uses something considerably smaller. Three reasons, and each one is a constant factor traded for a different resource, which makes them worth listing rather than waving at.

Double buffering. A merge that reads a block, waits, and then processes it leaves the device idle while it computes and the processor idle while it reads. Keeping two blocks per input — one being consumed, one being fetched — overlaps the two and halves the fan-in. That is a factor of two on k, which is a factor of log(2) on nothing at all when k is 65,536, and it is free in transfers. It is bought with memory and it buys latency, which is a resource this model does not have.

Larger reads. A block in this model is the unit the device moves; a block a system reads is chosen to make the device efficient, and for a spinning disk that meant reading a megabyte at a time to amortise a seek. Reading in units of 64B rather than B cuts the fan-in by 64 and cuts the number of seeks by the same factor. On a disk where a seek costs ten milliseconds and a megabyte costs eight, that is not a close call. On an SSD it is a much closer one, and the fan-ins in modern systems are correspondingly larger.

The merge itself is not free. Emitting the smallest of k heads costs a comparison per candidate if done naively — k per element, which at k = 65,536 is absurd — so real merges keep a heap or a tournament tree of the heads and pay log₂ k per element. That cost is in comparisons, which this model prices at zero, and at large fan-in it stops being negligible: log₂ 65,536 = 16 comparisons per element, against about 20 for an in-memory sort of the whole thing.

So the fan-in is chosen where the transfer count has stopped improving and the comparison count has started mattering, which is precisely the shape of every threshold in the practice phase — and, exactly as there, the shipped value is not the optimum of any single counter. It is where two counters cross.

What the run lengths do #

Run formation as described produces ⌈n/M⌉ runs of exactly M elements, and the pass count depends only on how many there are. That makes the initial phase look like a fixed cost, which it very nearly is, with one exception worth measuring.

If the input has structure — if it is nearly sorted, or arrives in sorted batches, as a log or a time series does — then the natural runs in it are longer than M and detecting them costs nothing. That is a run is a property of the input’s measurement applied one level out: the presortedness measure r, the number of natural runs, is exactly the number of initial runs an adaptive external sort would produce, and if r is below the fan-in the sort is one pass regardless of n.

This is not a small effect and it is why sorting a day’s log file is so much cheaper than sorting a random permutation of the same size. The site can state the mechanism precisely because it already measured the input’s shape as a number rather than as an adjective. What it cannot state is a class, because the class depends on the input distribution — and a bound whose exponent depends on the data is the bound with a precondition’s subject, not a fact about the algorithm.

The one number an operator can act on #

Everything above collapses to a single inequality, and it is worth extracting because it is the form in which this analysis is actually useful.

A sort is one pass when the number of initial runs is below the fan-in, that is when

$$\frac{n}{M} \le \frac{M}{B} - 1$$

which rearranges to roughly n ≤ M²/B. A gigabyte of memory and a 16-kilobyte block gives M²/B of about 64 terabytes: any file below that size sorts in two passes over the data — one to form runs, one to merge — and no amount of extra memory improves on it.

That single expression explains the shape of every external sorting system built since the 1990s. Two passes is the design target, it is reachable for essentially every file anybody sorts, and the entire engineering effort goes into making those two passes run at the speed of the device rather than into reducing their number. It also says exactly when the target is missed, which is when memory is small relative to the square root of the file — the case that used to be universal and is now unusual.

Where the next step is, and why nobody reaches it #

The inequality $n \le M^2/B$ gives the first step of the staircase. The rest of the steps follow from the same argument with the fan-in applied again: $p$ merge passes suffice when the run count $n/M$ is at most $k^p$, so

$$n \;\le\; M\left(\frac{M}{B}\right)^{p}.$$

Each additional pass multiplies the reachable file size by $M/B$, and $M/B$ is the enormous quantity from two sections above. At a gigabyte of memory and a sixteen-kilobyte block it is 65,536, so the steps land at about 64 terabytes, 4 exabytes, and 300 zettabytes.

That is the sharpest way to state what this field is about. The cost is a staircase, the staircase is genuine, and the whole of recorded computing sits on its first two treads. A three-merge-pass sort at these parameters would need a single file larger than the storage of any system ever built. The logarithm is real and its argument has nowhere to go.

The inequality is more useful read the other way round, as a statement about memory rather than about file size. One merge pass needs

$$M \;\ge\; \sqrt{nB},$$

so the memory required grows as the square root of the file. That single square root is why two-pass external sorting has stayed reachable through four decades in which data grew by orders of magnitude: a file a thousand times larger needs only thirty-two times the memory to keep sorting in two passes, and memory grew by considerably more than thirty-two over any period in which files grew by a thousand. The design target was not defended; it got easier.

The same expression says which parameter to watch, and it is not the obvious one. $M$ scales with $\sqrt{B}$, so a system that reads in larger units pays for it in the sort buffer: moving from a sixteen-kilobyte block to a megabyte — the change a spinning disk’s seek cost argues for, three sections above — multiplies the memory needed for a one-pass merge by eight, for the same file. The fan-in reduction discussed there as a constant factor on $k$ is a factor of eight on the threshold, and a threshold is where a third of the cost lives.

So the two engineering decisions are coupled in a direction that is easy to miss. Reading in bigger units makes each pass faster and makes an extra pass more likely, and which of those wins is not a question about either decision on its own. It is a question about where $\sqrt{nB}$ falls relative to the memory that happens to be available — the same shape as the cliff where the data stops fitting, with a square root in front of it, and the reason the floor under moving data is stated in transfers rather than in blocks read at a time.

Both parameters of the model move the pass count, and neither of them moves it the way the phrase a few passes implies.

The memory is the other half of the fanout, and it is the half an operator can actually change on a machine that already exists.

Neither of those extends the range, and a staircase is a claim about what happens next. The last sweep takes the original settings eight times further in $n$.

What changes about the choice of sort #

The in-memory question “which sorting algorithm” had an answer that filled several essays: it depends on the input’s presortedness, on whether stability is needed, on the cost of a comparison against the cost of a move, and on which of five counters is being paid.

Externally the question nearly disappears. The merge is not a choice, because it is the only shape that reads each block once per pass, and any algorithm that does not read each block once per pass is paying more than n/B for a pass it has to make anyway. Quicksort’s partition, applied externally, reads and writes the whole file per level of recursion with a fan-out of 2 or 3 rather than M/B, so it needs log₂ or log₃ as many passes as the merge needs log_{M/B} — a factor of fifteen at the numbers above, and it is not recoverable by any amount of engineering.

What remains a choice is the in-memory part, and this is where the practice phase reappears. Run formation sorts M elements at a time, in memory, by whatever the library provides — and that is Timsort or introsort or pdqsort, with all its thresholds, measured in the sort the library ships. The external algorithm’s structure decides the transfers; the internal algorithm’s policy decides the comparisons; and the two analyses do not interact at all, which is unusually clean and is the reason the field can be studied separately.

One real system detail is worth naming because it changes the constant by a factor of two. Run formation as described produces runs of exactly M elements. Replacement selection — keeping a heap of M elements and emitting the smallest that is still larger than the last one emitted — produces runs averaging 2M on random input, halving the number of initial runs and sometimes removing a whole pass. It is the one place where a cleverer in-memory algorithm changes the external cost, it works by exploiting the same presortedness a run is a property of the input measures, and modern systems mostly do not use it because a heap’s random access pattern costs more in cache than the pass it saves in transfers.

Which is this field’s own argument turned against it: a technique that wins in transfers and loses in the counter one level up. The hierarchy has more than two levels, and an algorithm optimal at one of them is making a claim about one of them.