The floor under every comparison sort

Almost everything in the analysis of algorithms is an upper bound. Somebody wrote an algorithm, somebody counted what it does, and the answer is that this much work suffices. A better algorithm might come along tomorrow, and often does.

A lower bound is a different kind of statement. It says that no algorithm does better — not the ones that exist, not the ones nobody has thought of, not the ones that will be invented in fifty years. It is a claim about an infinite set of programs, most of which will never be written, and it is not obvious that such a claim could be established at all.

For comparison sorting it can, and the argument is short enough to fit in a paragraph.

The argument #

Take any algorithm that sorts by comparing pairs of elements, and consider what it does on inputs of size $n$.

Each comparison has two outcomes. The algorithm’s behaviour is therefore a binary tree: the root is its first comparison, each node’s two children are what it does next depending on the answer, and a leaf is where it stops and produces an ordering. A run of the algorithm is a path from the root to a leaf, and the length of that path is the number of comparisons that run made.

Now, the algorithm must be able to produce every one of the $n!$ possible orderings. If two different input permutations led to the same leaf, the algorithm would produce the same output for both, and one of them would be wrong. So the tree has at least $n!$ leaves.

A binary tree of depth $d$ has at most $2^d$ leaves, so $2^d \ge n!$ forces $d \ge \log_2(n!)$.

Therefore some path is at least $\log_2(n!)$ long, which is to say: some input costs the algorithm at least that many comparisons. And the average path length in a binary tree with $L$ leaves is also at least $\log_2 L$, so the average over all inputs is at least $\log_2(n!)$ too — which is the stronger and more useful form of the statement.

That is the whole thing. No algorithm was examined, no code was read, and the conclusion applies to every comparison sort that has ever been or will ever be written.

Reading the four-element case concretely #

For $n = 4$ there are $4! = 24$ orderings. $2^4 = 16 < 24$, so no comparison sort can always finish four elements in four comparisons — some input will need five. $2^5 = 32 \ge 24$, so five might be enough, and in fact five is achievable.

The figure above is that statement drawn: a complete binary tree of depth four with all sixteen of its leaves, next to twenty-four orderings, eight of which cannot be assigned a leaf. There is no cleverness available. The eight orderings are not being handled badly; they are not being handled at all.

Worth noting what the argument does not assume. It does not assume the algorithm is deterministic in any particular way, that it compares adjacent elements, that it uses an array, or anything about how it decides which comparison to make next. It assumes only that the algorithm learns about the input exclusively through pairwise comparisons and that it must be correct on every input.

Computing the bound exactly #

$\log_2(n!)$ is wanted at sizes in the thousands, and the obvious implementation does not survive contact with a computer: $n!$ overflows a double-precision float at $n = 171$. Beyond that, Math.log2(factorial(n)) returns infinity.

The fix is to never form $n!$. Since $\log(ab) = \log a + \log b$,

$$\log_2(n!) = \sum_{k=2}^{n} \log_2 k$$

and summing a few thousand logarithms is instant and accurate. That is how the bound is computed here.

Accumulating thousands of floating-point additions invites error, though, so the sum is checked against an independent route. Stirling’s approximation gives

$$\ln(n!) \approx n \ln n - n + \tfrac{1}{2}\ln(2\pi n) + \frac{1}{12n}$$

and dividing by $\ln 2$ converts it. The two agree to better than five parts in ten million at every size the site uses, with the largest disagreement at the smallest $n$, which is exactly where an asymptotic approximation should be worst.

What the bound is worth in numbers #

At $n = 256$: $\log_2(256!) = 1{,}684$ comparisons. Nothing sorts 256 elements in fewer, on average, ever.

For scale, $n \log_2 n$ at $n = 256$ is $256 \times 8 = 2{,}048$. So the floor is about 18% below $n \log_2 n$ — the difference being the $n \log_2 e \approx 1.44n$ term, which is 369 comparisons here. That term shrinks relative to the total as $n$ grows, so the ratio $\log_2(n!) / (n \log_2 n)$ creeps towards 1, reaching about 0.89 by $n = 8{,}192$.

Which means: an algorithm whose comparison constant is 1.0 is asymptotically optimal, and one whose constant is 0.84 — as merge sort’s is — is below $n \log_2 n$ and much closer to the floor than to it. How close each algorithm actually gets is the natural next question and gets its own essay.

The floor over four ranges #

The floor is $\log_2 n!$ and the number everybody quotes is $n\log_2 n - 1.44n$, so the useful plate is the two of them together — and the useful check is that the gap between them behaves the same way wherever the axis is put.

Extending the right-hand end is the first variation, and it is the one an asymptotic claim is supposed to be about.

Moving the left-hand end matters more than moving the right, because that is where an approximation to a factorial has the least to work with.

The bound in bits #

There is a second way to state the theorem that some people find more intuitive, and it is the same statement.

Before the algorithm starts, the input could be any of $n!$ orderings, so the algorithm’s uncertainty is $\log_2(n!)$ bits. When it finishes it must have no uncertainty left — it has to know the answer. Each comparison returns one bit. Therefore at least $\log_2(n!)$ comparisons.

Put that way, “the information-theoretic floor” stops being jargon. It is literally a count of bits, the algorithm is literally acquiring them one at a time, and the bound is literally the amount it needs divided by the amount each question gives.

The bit framing also makes the escape routes obvious. Beating the bound requires either a question that returns more than one bit — which is what indexing by value does, since reading a bucket index supplies $\log_2 r$ bits at once — or less uncertainty to begin with, which is what knowing the data is nearly sorted amounts to. Both routes are used by real algorithms and both step outside the theorem rather than contradicting it.

It is worth noticing how much information sorting actually requires. Sorting a million elements means acquiring about 18.5 million bits, one comparison at a time. Sorting a billion means about 29 billion bits. The numbers are large because $n!$ is astronomically large, and $n!$ is astronomically large because there really are that many possible answers.

What “comparison” is doing in the theorem #

The bound applies to comparison sorts. That qualifier is not decoration, and understanding what it excludes is most of understanding the theorem.

The argument’s engine is that each comparison yields one bit. Distinguishing $n!$ possibilities requires $\log_2(n!)$ bits, and the algorithm cannot acquire them faster than one per comparison. If an algorithm can obtain information about the input some other way, the counting no longer applies.

Counting sort is the canonical case. Given $n$ integers known to lie in a range of size $r$, it makes an array of $r$ counters, walks the input incrementing them, then walks the counters emitting values. It performs zero comparisons and finishes in $\Theta(n + r)$ operations, which is linear when $r$ is $O(n)$.

There is no contradiction. Counting sort learns about an element by using its value as an address, which is an operation the decision-tree model does not have. It also demands something ordinary sorting does not: that the keys be small integers. Radix sort, bucket sort and every other linear-time sort make a comparable demand — and pay for it in an access pattern the hardware cannot anticipate.

So the theorem’s real content is: within the class of algorithms that can only ask “is $a$ less than $b$”, $\log_2(n!)$ is a wall. Escaping it requires leaving the class, and leaving the class requires knowing something about the values. The floor moves when the question changes, and by how much is measurable.

The bound as an instrument #

There is a practical use for a lower bound that has nothing to do with proving things, and it is the reason this site computes it on every build.

A measurement below the floor is a bug in the measurement. If the machinery ever reported a comparison sort averaging fewer than $\log_2(n!)$ comparisons, the correct conclusion would not be that information theory is wrong. It would be that a counter is not counting — an algorithm reaching past the instrumented primitives to touch the array directly, or a primitive that forgot to increment.

That failure is otherwise nearly undetectable. Every curve would still be a curve, every fitted exponent would still be right, because a constant factor missing from every measurement does not change a slope on logarithmic axes. The floor is a check that catches it, because the floor is an absolute number rather than a relative one.

So the site’s gate averages every sorting algorithm over sixteen random inputs at $n = 256$ and requires all ten to come in above 1,684. It also requires the best of them to come in near it — under 1.35 times — because a floor nothing approaches would be the wrong quantity to be plotting against, and the fact that merge sort lands at 1.02 is what makes the bound informative rather than merely valid.

Averages, worst cases, and a subtlety worth not glossing #

The bound as stated is about the average over all $n!$ input permutations, and it is important that a particular input can be sorted in far fewer comparisons than the floor.

Insertion sort sorts an already-ordered array of 256 elements in 255 comparisons. The floor is 1,684. There is no contradiction, and the resolution is that insertion sort achieves 255 on that input by being catastrophically bad on others — its average over random inputs is 16,317, nearly ten times the floor.

The decision tree makes this precise: a tree with $n!$ leaves can certainly have some short paths. What it cannot have is short paths everywhere, because there are not enough short paths to go round. Any algorithm that is fast on some inputs is paying for it on others, and the total is bounded below.

This is why the site’s floor assertions average over sixteen random seeds rather than measuring one run. Comparing a single run against an average-case bound would be comparing two different quantities, and it would fail — correctly — the first time somebody handed it a sorted array.

What the bound does not constrain #

Three things, and each is a place where the theorem’s precise wording matters.

It says nothing about writes. An algorithm could sort with $\log_2(n!)$ comparisons and an enormous amount of data movement, or with very few writes and many comparisons — selection sort does the second. There is no comparable floor for the write count, and the reason is that the decision-tree argument counts information acquired, which is a property of comparisons specifically.

It says nothing about time. An algorithm at the comparison floor with a terrible memory access pattern will lose on real hardware to one well above the floor with good locality. The bound is about a count, and the count is not the duration.

It assumes the $n$ outcomes are $n!$, and often they are not. The count of distinguishable outputs is where the whole argument starts, and it is $n!$ only when the keys are distinct. Give 256 values drawn from eight distinct ones and the orderings a sorting algorithm can tell apart number $256!/(k_1!\cdots k_8!)$ rather than $256!$ — 738.7 bits rather than 1,684, so the true floor is less than half of the number this essay has been computing. Merge sort spends 1,682 comparisons on such an input: at the permutation floor, and 2.3 times the floor that actually applies. The floor moves when the values repeat, which is a separate essay because the gap it opens is where three-way partitioning and counting sort live.

It says nothing about small $n$ in the way one might expect. The bound is exact at every $n$ — $\lceil\log_2 4!\rceil = 5$ is a hard fact about four elements, not an asymptotic statement. That is unusual and worth appreciating: most bounds in this subject are limits, and the difference between a limit and a value causes trouble elsewhere on this site. Here there is none.

Randomisation does not get under it #

A great many worst cases on this site are escaped by randomising, and it is worth establishing that this one is not — because the argument is short, because the conclusion is the opposite of the pattern everywhere else here, and because the reason for the difference is the interesting part.

A randomised comparison sort is a distribution over deterministic ones. Whatever coins it flips, once the coins are fixed the algorithm is a decision tree, so the randomised algorithm is a probability distribution over such trees.

Now average over uniformly random inputs. For each tree in the distribution, its average path length is at least $\log_2(n!)$ by the argument above. An average of quantities each at least $\log_2(n!)$ is at least $\log_2(n!)$. So the expected comparison count, averaged over both the coins and a uniformly random input, is at least the floor — and therefore some input exists on which the expected count is at least the floor.

That is Yao’s principle in its simplest form, and its conclusion here is flat: randomisation buys nothing against this bound. A randomised comparison sort has a worst-case expected count no better than $\log_2(n!)$, and randomised quicksort’s measured 1.24 times the floor is not a number that any amount of cleverness with coins reduces to 1.

Set that against what randomisation does elsewhere on this site and the contrast is sharp. It converts quicksort’s quadratic worst case into an expected linearithmic one; it converts a search tree’s degenerate spine into a logarithmic height; it converts a hash table’s colliding key set into an ordinary load. In every one of those the worst case was a fact about which input arrived, and moving the randomness into the algorithm took the input’s power away.

Here the worst case is not a fact about which input arrived. It is a fact about how many inputs there are, and no amount of randomness reduces $n!$. The coins can decide which comparisons to ask; they cannot make a comparison answer with more than one bit.

That gives a clean test for whether randomisation will help against any bound at all, and it is worth carrying past sorting. If the bound comes from an adversary choosing the input, randomising defeats the adversary. If it comes from counting the answers, randomising changes nothing, because the count of answers is not something the adversary controls. The floors on this site divide neatly along that line: the counting arguments — orderings, memory states, windows, texts with a given run count — are all immune, and the adversary argument for graph connectivity is the one where a randomised algorithm genuinely has something to gain.

Why lower bounds are rare #

Comparison sorting is one of a small number of problems where a tight lower bound is both known and easy. That is not typical, and it is worth saying why so the result is not over-generalised.

The decision-tree argument works because the output space is easy to count — there are exactly $n!$ orderings — and because the model of computation is restrictive enough to bound the information gained per step. Most interesting problems have neither property. For a great many, including some very famous ones, the best known lower bound is simply that the input has to be read, which is $\Omega(n)$ and usually far below the best known algorithm.

The gap between the best known upper bound and the best known lower bound is where most of the open problems in the field live. Comparison sorting is unusual in having no gap at all: the floor is $\log_2(n!)$, merge sort achieves within a few percent of it, and there is nothing left to find. That completeness is rare enough to be worth appreciating when it occurs.