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 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.

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 2.2% and the remaining 2.2% is structural. 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.