The floor under moving data

The floors field has one method and it has been applied to four questions so far: count the outcomes a computation must be able to distinguish, count how much each step of the computation can distinguish, and divide. That gives log₂(n!) comparisons for sorting, log₂(n+1) for searching, and a bound on the bits a filter needs.

Applied to a file on a disk, the same method gives a different and less familiar expression, and the whole interest of this essay is that the answer is not the old bound with a factor of B taken out of it.

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

Where the expression comes from #

The argument is Aggarwal and Vitter’s and it is a counting argument of exactly the shape the floor under every comparison sort uses. What differs is what a single step can learn.

In the comparison model, one step is one comparison and it yields one bit: two outcomes, so an algorithm making c comparisons distinguishes at most 2^c orderings, and since it must distinguish n! of them, c ≥ log₂(n!).

In the external model, one step is one block transfer, and a transfer can yield far more than a bit. Bringing in a block of B elements and having M/B blocks already resident permits the algorithm to learn the relative order of the arriving B elements against everything in memory. The number of orderings that one transfer can newly resolve is bounded by the number of ways B elements can be interleaved with the M already there — a binomial coefficient — and taking logarithms, one transfer is worth at most about

$$B \log \frac{M}{B}$$

bits of ordering information.

The rest is division. The algorithm must resolve log₂(n!) ≈ n log₂ n bits in total; each transfer supplies at most B log(M/B) of them; so the number of transfers is at least

$$\frac{n \log n}{B \log (M/B)} = \frac{n}{B} \cdot \frac{\log n}{\log (M/B)} = \frac{n}{B}\log_{M/B} n$$

and the n/B inside the logarithm rather than n comes from being slightly more careful about what the initial run formation can be credited with.

Every term in that expression is doing work, and each one is a different resource. The n/B in front is a scan: no algorithm can cost less than reading its input. The n/B inside the logarithm is the number of blocks to be ordered. The base M/B is how much ordering one pass can accomplish, and it is the only place the memory size appears.

Why this is a floor and not a description of merge sort #

The distinction matters more here than in the comparison model, because the bound and the algorithm look so similar that they can be mistaken for each other.

The upper bound — external merge sort’s cost — is 2(n/B)(1 + ⌈log_k(n/M)⌉) with k = M/B − 1, derived in sorting what will not fit by counting the passes the algorithm makes. It is a fact about that algorithm.

The lower bound is a fact about the problem. It says that no algorithm whatever — not a cleverer merge, not a distribution sort, not something nobody has thought of — can sort in fewer transfers, in this model, for any input. The argument never mentions merging. It counts information and divides.

That the two agree to within a constant is the interesting result, and it is not the usual situation. The comparison floor log₂(n!) is met to within 1% by a careful merge sort, which is why how close anything gets to the floor can measure the gap so precisely. Here the constant is between two and three, and this site’s habit is to say what it is made of rather than to absorb it into a Θ.

What the measured constant is made of #

The ratio in the figure runs 2.40 to 2.97 and is not noise. Three identifiable components, and they add up:

A factor of two for writing. The bound counts the transfers needed to learn the order. A merge sort also has to write the result down, and every pass writes as much as it reads. The bound as usually stated does not charge for output; the algorithm pays for it on every pass, so the measured cost is double the bound’s read-only accounting before anything else happens.

A ceiling on the pass count. ⌈log_k(runs)⌉ is an integer and log_{M/B}(n/B) is not. At n = 4,096 with B = 32 and M = 512 the ideal pass count is about 1.6 and the algorithm makes 2, which is a factor of 1.25 for nothing but rounding up. That is the same staircase measured in the previous essay, seen from the bound’s side.

Run formation. The first pass reads and writes the whole file to produce runs of M, and the bound gives credit for it in the n/B rather than n inside the logarithm — a discount that is exactly right asymptotically and slightly generous at these sizes.

Multiply the first two and 2.5 is already accounted for. The remaining variation with n is the ceiling moving through its steps, which is why the ratio is not constant: it is 2.86 where the pass count has just ticked over and 2.40 where the size has grown into a pass it was already paying for. The gap to the floor is not a property of the implementation’s quality here — it is mostly the difference between a real algorithm’s integer pass count and a bound’s real-valued logarithm.

The floor moves when the parameters do #

The comparison floor log₂(n!) depends on n alone. This one depends on n, B and M, and that changes what kind of statement it is.

Doubling B halves the floor: fewer, larger transfers move the same data. Doubling M does not halve anything — it changes the base of a logarithm, which at realistic sizes usually changes nothing at all, and occasionally removes an entire pass. A floor with parameters is not a single number, it is a surface, and an algorithm sitting on it at one (B, M) may be far above it at another.

This is the floor moves when the question does’s argument arriving from a new direction. There, the floor changed because the question changed — sorting with duplicates has a lower floor than sorting distinct keys, and the difference is exactly the entropy of the multiset. Here the question is fixed and the machine changes, and the floor moves with it.

There is a limiting case worth stating because it makes the parameters concrete. When M ≥ n — the whole file fits in memory — the expression degenerates: log_{M/B}(n/B) falls below one, the bound becomes the scan n/B, and it is correct. Sorting data that fits costs one read, because the sorting itself is free in this model. The model does not stop working when the data fits; it says that the interesting quantity has gone to zero, which is the right behaviour for a model and is not what a bound stated only as Θ((n/B)log(n/B)) would suggest.

What the bound does not cover #

Two exclusions, both of which matter and neither of which is an oversight.

It is a bound on comparison-based sorting, or more precisely on algorithms that learn the order only by comparing. A radix sort on integers of bounded width does not, and beats it, exactly as counting sort beats log₂(n!) in the comparison model. The external radix sorts used in real systems are not violating anything; they are answering a different question, the one where the keys carry structure. This is the same exclusion the floor when the values repeat drew around the comparison floor, and it is worth restating because the external version is exploited far more often in practice — most large sorts in real systems are of fixed-width keys.

It assumes one disk and one processor. The original paper’s second result is about D parallel disks, where the bound divides by D and achieving it is a real problem in itself, because the blocks have to be spread across the disks so that every pass can read from all of them at once. Nothing here is measured with parallelism, and every number in this field is a number for a machine with one path to its data.

The gap at three settings of the model #

The bound is $(n/B)\log_{M/B}(n/B)$ and the algorithm above it is a real run, so the distance between them is a measurement and moves with the two parameters.

Neither of those extends the range, and the shape of the gap over $n$ is the part of the claim that a short sweep cannot settle.

Two more floors in the same model, and one of them is a surprise #

The sorting bound is the famous one. Two others are worth stating because between them they show what the model’s floors look like as a family.

Searching is log_B n and the B-tree meets it. An algorithm that has read t blocks has seen at most tB keys, and each block it fetches can eliminate at most a fraction of the remaining candidates equal to what its B keys can separate — which gives Ω(log_B n) transfers to locate one key among n. A B-tree achieves it. That is a tight bound, met by a structure in production since 1970, and it is the reason a tree with nodes the size of a block can say a B-tree is optimal rather than merely good.

Permuting is the surprise. Given n elements and a permutation π stated in advance, rearrange them. No comparisons are needed — the answer is supplied — so intuition says this must be cheaper than sorting, and the elements must simply be moved: n/B transfers, the cost of a scan.

It is not. The bound is

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

which says that permuting costs either one transfer per element, or as much as sorting, whichever is smaller. Moving each element individually costs n; using the sorting machinery costs the sort bound; and there is nothing in between.

The reason is that a permutation destroys locality by definition. To move B elements into one output block they must be gathered from B different places, and gathering is the operation the model charges for. Knowing where each element goes does not help, because the cost is in the moving rather than in the deciding.

So the information the comparison model spends all its effort acquiring turns out to be nearly worthless in this one. In the comparison model, being handed the answer reduces sorting from n log n to n. Here it reduces the bound by nothing at all for any realistic B and M — since n/B · log_{M/B}(n/B) is below n whenever the logarithm is under B, which it always is. That is a genuinely strange result, it is a fact about the model rather than a curiosity, and it explains why external algorithms that “just rearrange” are never cheap.

What it means for a bound to be met #

The site has now measured three different relationships between a floor and an algorithm, and the external sorting bound is the third kind.

Met exactly. The comparison floor for searching is ⌈log₂(n+1)⌉ and binary search performs exactly that. There is no gap and no constant to measure.

Met to within a per cent. The comparison floor for sorting is log₂(n!) and merge sort is within 1% of it at the sizes how close anything gets to the floor measures. The gap is real, it is small, and it is entirely due to merge sort’s inability to use fractional comparisons.

Met to within a small constant, where the constant is structural. That is this one: 2.40 to 2.97, and the components are identifiable rather than mysterious — a factor of two for writing the answer down, a ceiling on the pass count, and a discount on run formation. A constant that can be decomposed is a different object from a constant that cannot, and the difference is the whole reason this site measures gaps rather than quoting classes.

There is a fourth relationship this field does not exhibit and it is worth naming because its absence is informative: no algorithm here beats the floor by exploiting structure the bound did not consider. The comparison field has that case — counting sort beats log₂(n!) because it does not compare — and its external analogue exists too, in radix-based external sorts. It is excluded from the bound rather than beating it, which is the same relationship and not a counterexample.

What the bound looks like from the algorithm’s side #

A floor is worth more when it explains a design rather than merely constraining one, and this one explains the two decisions that give external merge sort its shape.

Why merge at all, rather than partition. A distribution sort splits the file into buckets by key range and recurses. Its fan-out is limited by exactly what a merge’s fan-in is limited by — one output block per bucket in memory — so it makes the same number of passes and meets the same bound. Externally, merging and partitioning are the same algorithm read in two directions, which is not true in memory, where quicksort and merge sort have genuinely different characters. The bound predicts that, in the sense that any algorithm meeting it must be moving the whole file log_{M/B}(n/B) times, and there are not many ways to arrange that.

Why the fan-in is maximised rather than balanced. In memory, merging 2 runs at a time and merging 32 at a time do the same total comparison work, so there is no reason to prefer either. Externally, the fan-in is in the base of the logarithm, so every increase reduces the pass count directly. The bound says the pass count is the only quantity that matters, and the algorithm is therefore built to make it as small as the memory permits — which is why the first thing any external sort does is compute M/B.

Both of those are cases of a floor being constructive: it does not merely say what cannot be beaten, it says which quantity a design has to attack. That is the most useful thing a lower bound ever does and it is rarer than the bounds themselves.

The constant is two, and the rest is a sawtooth #

Between two and three, and structural is the right diagnosis and it can be closed. Write both sides out and the ratio has a closed form.

The algorithm costs $2(n/B)\,p$ transfers, where $p = 1 + \lceil\log_k(n/M)\rceil$ is its pass count. The floor is $(n/B)\log_{M/B}(n/B)$. So

$$\text{ratio} \;=\; \frac{2p}{\log_{M/B}(n/B)}.$$

At $B = 32$ and $M = 512$ the base is 16, so the denominator is 1.25, 1.50, 1.75, 2.00, 2.25 and 2.50 across the sweep, and the pass count is 2, 2, 2, 3, 3, 3. That gives ratios of 3.20, 2.67, 2.29, 3.00, 2.67, 2.40 — and the measured range is 2.40 to 2.97, so the model reproduces both endpoints of the plotted band to within a per cent.

Which says the shape rather than merely the size. The ratio is a sawtooth. Inside a pass regime the numerator is fixed and the denominator grows with $n$, so the ratio falls steadily; when the ceiling ticks over, the numerator jumps by $2$ and the ratio jumps with it. The band 2.40–2.97 is not a scatter and not a trend — it is one tooth, and a longer sweep would draw the same tooth again with a smaller amplitude.

Smaller, because the amplitude is $(p+1)/p$. From two passes to three the jump is a factor of 1.5; from three to four, 1.33; from ten to eleven, 1.10. So the ratio converges on exactly 2 as $n$ grows, and the two is the write factor — the bound counts the transfers needed to learn the order and the algorithm also writes the answer down, once per pass.

That closes the decomposition into a statement with no residue. The gap between an external merge sort and the sorting floor is a factor of two, permanently, for output the bound does not charge for, times a sawtooth of $\lceil x\rceil/x$ on the pass count that goes to one. There is nothing else in it — no implementation slack, no constant nobody has accounted for, and the run-formation discount this page names as a third component is already inside the pass count’s $+1$.

It also makes the ratio predictable rather than measurable, which is the useful form. Given $n$, $B$ and $M$, both the pass count and the logarithm are arithmetic, so the distance to the floor is computable before anything runs — and a system finding itself at 3.0 rather than 2.4 knows it has just crossed a pass boundary and that a slightly larger $M$ would put it back. Sorting what will not fit measures the staircase from the algorithm’s side; this is the same staircase divided by a smooth curve, which is why the quotient wobbles rather than settling, and why how close anything gets to the floor’s single-number style of report does not survive a model with parameters in it.

Why this floor is the more useful one #

The comparison floor is the more elegant result and the external one is the more consequential, for a reason that is worth being blunt about.

The comparison floor is almost never the binding constraint. Merge sort is within 1% of it, every library sort is within a small factor, and the difference between the best and worst sensible sorting algorithm in comparisons is a factor of three. Nobody’s system is slow because their sort makes 1.4·n log₂ n comparisons instead of n log₂ n.

Systems are routinely slow by factors of tens because a sort spilled to an extra pass, or because an access pattern turned a scan into random reads. Those are transfer-count failures, they are what this floor is about, and the gap between a good and a bad algorithm here is not a factor of three — it is a factor of B, which is a few hundred to a few thousand.

The floor whose neighbourhood everybody already occupies is the less interesting one to measure, and this field exists because the site had been measuring that one exclusively for four phases.