How close anything gets to the floor

Given a bound that nothing can cross, every algorithm acquires a number: how far above it does this one sit?

That number is more useful than the complexity class, and it is not published anywhere. Everyone knows merge sort and heapsort are both $\Theta(n \log n)$. Rather fewer know that at $n = 256$ merge sort averages 1,722 comparisons against a floor of 1,684 — 2.2% above optimal — while heapsort averages 3,300, which is 96% above.

One of those algorithms has essentially no room left for improvement. The other has a factor of two on the table.

The measurements #

At $n = 256$, averaged over sixteen independent random inputs:

The averaging matters. A lower bound on the average case is a statement about a distribution, and comparing a single run against it would be comparing two different things — an individual input can be sorted in far fewer comparisons than the floor, and an already sorted array costs insertion sort 255.

Merge sort at 1.02 #

An algorithm within 2.2% of a bound that no algorithm can beat is a remarkable object, and it is worth understanding why merge sort manages it.

The decision-tree argument says a perfect algorithm extracts one full bit of information per comparison. Merge sort nearly does. When merging two sorted runs, each comparison determines exactly one element of the output — the smaller of the two front elements goes next — and that determination is never revisited. No comparison is repeated and no comparison’s result is discarded.

The 2.2% is the small amount of waste at the ends of the merges, where one run empties and the remainder of the other is copied without comparison. Those copied elements are placed for free, which sounds like a saving and is actually the source of the gap: the algorithm ends up knowing slightly less per comparison than it could.

The gap also shrinks with $n$. The floor’s ratio to $n \log_2 n$ climbs towards 1 as $n$ grows, and merge sort’s constant is 0.838, so merge sort is asymptotically below $n \log_2 n$ and converging on the floor from a fixed small distance.

There is a practical consequence. Where cost is dominated by comparisons — sorting strings, sorting by a user-supplied comparator, sorting anything where the comparison is a function call — then merge sort is not merely a good choice. It is within a couple of percent of the best any algorithm can do, and effort spent looking for something better is effort spent looking for at most 2%.

Heapsort at 1.96, and why #

Heapsort’s factor of two has a specific cause, and it is structural rather than incidental.

The sift-down operation moves an element down the heap to restore the heap property. At each level it must decide which of the two children to descend into, which takes one comparison, and then decide whether to descend at all, which takes another. So each level of the descent costs two comparisons where merge sort’s merge costs one per output element.

The comparison that picks the larger child is not wasted exactly — it is needed — but its result contributes nothing to the final order. It selects a direction. Only the second comparison at each level says anything about where the element belongs. Roughly half the comparisons are navigation.

That is the factor of two, and it is not removable without changing the algorithm. Bottom-up heapsort — a variant that descends to a leaf first and then walks back up — reduces it substantially, and is a good example of a change that is invisible in the complexity class and worth a great deal in the constant.

Heapsort keeps its place in the standard repertoire for a different reason: it is $\Theta(n \log n)$ in the worst case with no bad inputs at all, and it sorts in place. Quicksort has a quadratic worst case and merge sort needs a buffer. Heapsort’s factor of two is the price of a guarantee.

The quadratic sorts, in perspective #

Selection sort at 19.38 times the floor is a number that makes the classification look coy.

“Quadratic” and “linearithmic” are two categories, and the language treats the gap between them as a single step. At $n = 256$ it is a factor of nineteen. At $n = 4{,}096$ selection sort performs 8,386,560 comparisons against merge sort’s 43,976 — a factor of 191. At a million elements it would be a factor of about 30,000.

The ratio to the floor makes this visible in a way the class does not, because it is a number rather than a label, and because the same number applies to everything on the page. It also flatters insertion sort slightly relative to its reputation: at 9.69 it is twice as good as selection sort and bubble sort on random input, and on nearly sorted input it is better than everything else on the site, which no summary describing it as quadratic conveys.

The ratio at four sizes #

The ratio is the whole of the essay and it is a ratio at a size, so it is worth having at four of them before anything is said about how it moves.

A third size makes the direction readable rather than guessable, because two points define a line and three of them are the first evidence that it is one.

The trial count is the other dial, and it decides how much of each algorithm’s own spread is in the number.

The ratio at other sizes #

A ratio measured at one size invites the question of whether it holds at others, and for these algorithms it mostly does — with one systematic drift worth knowing about.

The floor is $\log_2(n!) \approx n\log_2 n - 1.44n$, and the linearithmic algorithms’ counts are $c \cdot n \log_2 n$. So the ratio is

$$\frac{c \cdot n \log_2 n}{n \log_2 n - 1.44n} = \frac{c}{1 - 1.44/\log_2 n}$$

which decreases towards $c$ as $n$ grows. Merge sort’s ratio of 1.02 at $n = 256$ is on its way down to 0.838 — which is below 1, meaning merge sort is asymptotically better than $n \log_2 n$, and the gap to the floor closes rather than widening.

For the quadratic algorithms the drift goes the other way and is much larger: selection sort’s ratio of 19.4 at $n = 256$ becomes about 191 at $n = 4{,}096$, because the numerator grows like $n^2$ and the denominator like $n \log n$.

So the ratio is a snapshot, and the snapshot is taken at $n = 256$ throughout this site. That size is chosen because it is where the quadratic algorithms are still affordable to average over sixteen seeds and the floor is already meaningful. Anyone quoting these numbers should quote the size with them, in the same way that a constant needs its input distribution.

Why the gate requires the floor to be tight #

A lower bound that nothing comes near says very little. If the best available algorithm were forty times the floor, the honest reading would be that the bound is loose — that some stronger argument would give a higher floor — rather than that everyone’s algorithms are bad.

So the site’s gate makes two demands, not one:

• nothing may average below the floor — which catches an instrument that has stopped counting properly
• the best algorithm must come within 1.35 times it — which catches a bound that is not worth plotting against

Merge sort at 1.02 passes the second comfortably. If a future change to the merge implementation pushed it to 1.5, the gate would fail and the failure would be informative: either the implementation got worse or the bound is being computed wrongly.

The pair of requirements is the same shape as choosing a fit tolerance: a number is only defensible when it is bracketed by two things that were themselves measured.

The ratio is a mean, and the mean has a range #

Every number in the table is a mean over sixteen inputs, and the underlying quantity is a distribution. For the deterministic algorithms — merge sort, heapsort, the quadratic three — the distribution is narrow to the point of being uninteresting: merge sort’s comparison count varies by under a percent across seeds, because its work is determined by the shape of the recursion rather than by the data.

For the randomised ones it is wider, and the width is worth seeing beside the floor rather than only as a single point above it.

The distance-to-floor ratio for randomised quicksort is 1.24 as a mean and runs from about 1.15 to about 1.55 across individual runs at n = 256. Quoting the mean is defensible and quoting only the mean is the omission the wrong field is about.

What the ratio does not capture #

Three things, and they are the same three that limit every single-number summary on this site.

It is a comparison ratio. Selection sort at 19.38 does 1,008 writes at $n = 512$ where insertion sort at 9.69 does 63,074. By the write count, the ranking inverts completely. There is no floor theorem for writes, so no equivalent ratio exists, and the choice of count is doing all the work.

It is an average. Randomised quicksort at 1.24 is 1.24 on average and has a tail. Quicksort with a first-element pivot measures 1.23 here — marginally better than the randomised version on random input — and costs 130,816 comparisons on a sorted array of 512, which is 78 times its random-input mean. The ratio at one input distribution says nothing about the others.

It is not time. An algorithm 2% above the comparison floor can be several times slower than one 96% above it, if the first one’s memory access pattern is bad enough. That is the machine field’s subject, and heapsort — the worst algorithm on this page by the floor ratio — is a good example, because its problem on real hardware is not the extra comparisons at all.

Where the remaining 2% goes #

Saying that merge sort is 2% above the floor invites the obvious question, and the obvious question has an exact answer rather than a hand-waving one.

The floor decomposes. Merge sort builds a binary tree of merges over singleton leaves, and for any such tree the product of the binomial coefficients $\binom{p+q}{p}$ over the merges is exactly $n!$ — every permutation is determined by choosing, at each merge, which of the interleavings of the two sorted runs occurred. So

$$\log_2(n!) \;=\; \sum_{\text{merges}} \log_2 \binom{p+q}{p}$$

and each merge has its own floor: the number of bits its interleaving carries. The excess is then attributable merge by merge, and the attribution can be measured by recording the comparisons each merge actually spends beside the bits it was entitled to.

At $n = 4{,}096$, averaged over twenty-four seeded inputs, merge sort spends 43,971 comparisons against a floor of 43,250 — an excess of 721. Grouped by the width of the merge:

Three things fall out of that table, and none of them is what the phrase “the constant is slightly above optimal” suggests.

The bottom of the tree is perfect. Merging two singletons costs exactly one comparison and carries exactly one bit. Half of all the merges merge sort performs are optimal with nothing left over, and the algorithm’s inefficiency begins at the second level.

The waste per merge grows with the merge, and the number of merges shrinks faster. A width-4,096 merge throws away four comparisons; a width-4 merge throws away 0.078. But there are a thousand of the small ones and one of the large one, so the small merges lose fourteen times more in total. Two thirds of the entire excess is in merges of 32 elements or fewer.

The single largest merge — the one that does a quarter of all the comparing — is 99.9% efficient. The intuition that the top of the recursion is where the work and therefore the waste is turns out to be exactly backwards.

That also explains why the ratio improves with $n$: 1.026 at $n = 256$, 1.023 at 512, 1.017 at 4,096, all over the same seeds. Growing the input adds levels at the top, and the levels at the top are the efficient ones.

So the 2% is structural in a specific and locatable sense: it is the cost of merging small runs, it is where a merge cannot use a whole comparison’s worth of information, and no rearrangement of the same merges would recover it. The algorithms that do get closer — the merge-insertion family — get closer by changing which merges happen, and pay for it in data movement and in code nobody wants to maintain.

The general shape of the idea #

Measuring an algorithm against its competitors identifies the best among the ones somebody thought of. Measuring it against a proved bound establishes how much room is left in principle.

The second question has an answer for comparison sorting, and the answer is: almost none. Merge sort is within a couple of percent, and the section above locates every comparison of that remainder in the merges near the leaves. Anyone hoping to make a substantially better comparison sort is hoping for something the mathematics forbids.

That is an unusual position for a computational problem to be in, and it depends on the bound being about a question rather than an algorithm. For most problems the gap between the best known algorithm and the best known lower bound is enormous, and closing it is where the research is. Sorting is finished, and knowing it is finished is worth something — it says where not to look, which is the most useful thing a lower bound does.

The same decomposition, for every other algorithm #

The merge-by-merge attribution is the most useful thing in this essay and it is written for one algorithm. The idea generalises, and stating the general form says what a second instrument would look like.

A comparison sort’s state, at any moment, is the set of permutations still consistent with the outcomes it has seen. A comparison that splits that set in half yields a full bit; one that splits it unevenly yields less; one whose outcome was already determined yields nothing at all. The excess over the floor is the sum, over every comparison, of the bit it failed to extract.

That is a computable quantity rather than a metaphor. Maintain the consistent set explicitly, and after each comparison record $\log_2$ of the ratio between its size before and after. For $n = 8$ the set starts at 40,320 permutations, which is small enough to hold and walk, and this collection’s habit is to perform an argument at a size a figure can carry rather than to assert it at a size it cannot.

Run that instrument over the algorithms in the table and the causes become measurements instead of explanations. Heapsort’s factor of two is attributed above to navigation comparisons — the ones that pick which child to descend into — and the claim is that their outcomes contribute nothing to the final order. That is exactly a claim that those comparisons yield zero bits, and the instrument would say so or refute it.

It would also settle the quadratic sorts, where the diagnosis is currently a shrug. Selection sort at nineteen times the floor is performing comparisons whose outcomes it discards — it finds a minimum, and everything it learned about the relative order of the non-minima is thrown away at the end of the pass. An information-yield measurement would put a number on how much, and the number would be the algorithm’s whole story.

It is not built here. What is built is the merge decomposition, which is the same idea specialised to a case where the arithmetic closes in one line, and the generalisation is named so that the specialisation is not mistaken for a trick.

Which sorting question is finished #

The closing claim above needs one qualification, and it is the difference between two floors that are the same number and two problems that are not.

Everything in this essay measures the average number of comparisons against $\log_2(n!)$, and by that measure merge sort is within a couple of per cent and there is nothing left to find. That question is settled.

The worst-case question is not. The floor is the same — a decision tree of $n!$ leaves has depth at least $\lceil\log_2 n!\rceil$ whichever case is being measured — and the best known algorithm is further from it. Merge-insertion sort, from Ford and Johnson, matches the floor exactly for small $n$ and is known not to for all $n$; how large the true worst-case optimum is remains open, and the gap is a handful of comparisons rather than a constant factor.

So the honest statement is narrower than “sorting is finished”. Sorting is finished on the average case, to within two per cent, by an algorithm anybody would actually run. On the worst case there is a small open question, its answer is worth a few comparisons per sort, and nobody would deploy the algorithms that chase it because their data movement is dreadful.

That distinction is worth keeping because it is the shape of a mature problem rather than a solved one: the practically interesting question is closed and the theoretically interesting one is open, and the remaining gap is small enough that closing it would change nothing about what anybody runs.