The questions a sort asks twice

The floor under every comparison sort is an argument about counting leaves: the answer is one of $n!$ orderings, each comparison has two outcomes, so no algorithm averages fewer than $\log_2 n!$ comparisons. On 256 elements that is 1,684 comparisons, and selection sort makes 32,640.

The usual account of that gap is asymptotic — one algorithm is quadratic and the other is not — and it explains nothing about what the extra comparisons are doing. This page opens them.

A sort’s comparisons build a partial order, and the partial order’s transitive closure answers more questions than were asked. If a sort has established $a < b$ and $b < c$, it already knows $a < c$, and a comparison between them can only confirm it. Such a comparison eliminates no ordering at all. It is, in the exact sense the floor is about, free of information.

How many are already answered #

The closure is maintained exactly while each sort runs, as bitsets of predecessors and successors, and the sort is handed a comparator that consults it. Nothing about the algorithm changes: a comparison sort learns about its input only through the comparator, so replacing the comparator is the one intervention that leaves the algorithm what it was.

Five of the ten never ask a question they have already answered, and the division does not follow the complexity classes. Insertion sort is quadratic and repeats nothing; heapsort is linearithmic and repeats a quarter of its questions.

The two quadratic sorts that do repeat are the page’s easiest finding. Selection sort scans the remaining range for its minimum on every pass, and the second pass re-compares elements whose relative order the first pass established — 19,561 comparisons of 32,640. Bubble sort’s later passes re-compare adjacent pairs it has already settled: 16,033 of 32,585.

What removing them would buy #

Not enough, and that is the page’s real argument.

Strip every repeated question from selection sort and 13,079 comparisons remain — still 7.8 times the floor. Strip them from bubble sort and 16,552 remain, 9.8 times the floor. A hypothetical selection sort with perfect memory would be no better than a bad linearithmic sort.

So redundancy is not where a quadratic sort’s cost is. It is a large share of it and it is not the mechanism.

The arithmetic is worth doing slowly, because the share and the ratio pull in opposite directions and it is easy to read the larger of the two as the more serious. Selection sort’s 59.9% is the bigger-looking number and it accounts for a factor of 2.5. Its remaining comparisons are the smaller-looking number and they account for a factor of 7.8. A defect that explains a quarter of a gap is not the explanation of the gap, however large its percentage looks written down, and the only reason the percentage looks like the explanation is that nothing else on the page had been measured yet.

That identity is exact at every size drawn and it is not a coincidence. Both sorts learn the order by comparing adjacent elements and moving the smaller one left, so the set of new facts each establishes is the same set: one comparison for each inversion, plus one for each place the scan stops. Insertion sort asks each of those once. Bubble sort asks each of them once and then asks a great many of them again, because it has no record of which pairs it has settled.

The phrase “new facts” is doing work there and can be made precise. A comparison is new when the pair it names is incomparable in the closure of everything asked so far, and for a sort that only ever compares neighbours in the current arrangement the incomparable neighbouring pairs are exactly the ones still out of order, plus the pair at which a scan stops. Insertion sort’s inner loop walks left until it finds a key no larger, so it asks one question per inversion crossed and one to stop; bubble sort’s pass does the same thing across the whole array, discards what it learned at the end of the pass, and begins again.

So bubble sort is insertion sort with amnesia, in a sense that can be measured rather than gestured at, and curing the amnesia would make it insertion sort exactly — which is still quadratic.

The other kind of waste #

If removing every repeat leaves insertion sort’s cost, and insertion sort repeats nothing, then insertion sort’s cost is not redundancy. It is something else, and the something else can be measured too.

The orderings still consistent with what a sort knows are the linear extensions of the partial order its comparisons have built, and they can be counted exactly by a walk over subsets. A comparison’s information is then the logarithm of the ratio between the counts before and after it: a comparison that halves the space carries one bit, a repeated one carries zero, and most carry something in between.

Insertion sort repeats nothing and still removes only 0.716 of a bit from each question. Merge sort removes 0.963. The difference is small in a ratio and it is the whole of the difference in class, because it compounds over every comparison: a sort that gets 0.72 bits from each question needs $\log_2 n! / 0.72$ questions and one that gets 0.96 needs $\log_2 n! / 0.96$ — except that the shortfall is not constant, and a sort whose questions get steadily less informative as it proceeds is exactly a sort whose count grows faster than the floor.

That is what insertion sort does. Comparing a new key against the sorted prefix asks “is this key smaller than that one” when the answer is very likely no — and an answer that is likely removes little. Merge sort’s merge compares the fronts of two runs that are entirely incomparable, so either answer is about equally likely and the comparison is close to a full bit.

The two sequences sum to the same number by construction — every sort must remove $\log_2 n!$ bits, since it starts with $n!$ orderings and finishes with one — so the only question is how many comparisons it takes to remove them, and that is the mean height of the bars.

Merge sort’s bars are tall and nearly uniform, and the last is worth two bits: the final merge’s last comparison resolves the only ambiguity left, which by then is a choice between four orderings rather than two. Insertion sort’s are ragged and mostly short, and the pattern is legible — a run of small bars as a key is compared against a long sorted prefix it belongs near the end of, then a tall one when the scan finally stops.

The dark bars clustering at the end is a remark about when a sort stops learning rather than about how much it learns. Both of these sorts spend their last third of comparisons confirming an order they have essentially finished establishing, which is the visual form of the arithmetic above.

The share that is not a share #

There is a temptation, having a percentage, to treat it as a budget: selection sort wastes 60% of its comparisons, so a perfect selection sort would be 2.5 times faster. The plates above say that reading is wrong twice over.

It would be 2.5 times cheaper and still 7.8 times the floor, which is the arithmetic of the second section. A fix that removes the whole of a measured waste and leaves the method eight times worse than necessary is a fix worth having only if nothing better is available, and something better is: one run, four counts, four answers has nine other sorts on the same plate.

And the 60% is not a share of the work a machine does. A repeated comparison costs exactly what a new one costs — a load, a compare, a branch — so the percentage is a share of questions rather than of time, and the only sense in which the repeats are waste is the information-theoretic one. That is the sense the floor is stated in, which is why the measurement belongs beside it, and it is not the sense a profiler would report. The count is not the time is the standing caution and it cuts both ways here: a count can overstate a cost as easily as understate it.

The second measurement is the first one turned over #

A reader who has got this far has two numbers for each sort and should be told what the second one is not.

Every sort removes exactly $\log_2 n!$ bits, because every sort starts with $n!$ orderings and ends with one. So the mean bits per comparison is $\log_2 n!$ divided by the comparison count, and as a ranking of sorts it carries no information the count did not already carry. The bits plate’s order — merge, first-element quicksort, random-pivot quicksort, Shellsort, insertion sort, median-of-three, heapsort, bubble, selection — is the comparison count’s order written backwards, and it could not have been anything else.

What the second measurement buys is three things, and none of them is a ranking.

It prices a single comparison, which a count cannot. That is the whole of the trace plate: the mean is arithmetic, and the shape around it is not.

It gives the gap to the floor a unit. Merge sort makes 19.3 comparisons where the floor is 18.47, and saying it removes 0.963 of a bit rather than a full one states the same fact in the currency the floor is stated in. A ratio of counts is a number; a shortfall in bits per question is a diagnosis.

And it contains the first measurement exactly. A comparison removes zero bits precisely when its answer was already implied — so the repeats are not merely similar to the uninformative comparisons, they are the ones priced at exactly zero. The two quantities are computed by two procedures that share nothing: one maintains a transitive closure as bitsets of predecessors and successors, the other counts linear extensions by a walk over subsets and takes a logarithm. They agree to the comparison on every sort at every size checked — Shellsort 1.8 and 1.8, median-of-three 11.0 and 11.0, heapsort 11.9 and 11.9, bubble 7.8 and 7.8, selection 14.5 and 14.5.

That agreement is worth more than either number. It says the first section measured a boundary case of the second and not a different thing, which is what makes the sentence at the head of the next section a statement about one quantity rather than a comparison of two.

Two different defects, and one is not the other #

The page now has two quantities and they rank the sorts differently.

Repeats put selection sort worst at 59.9% and insertion sort joint-best at zero. Bits per question put selection sort worst at 0.513 and insertion sort seventh of ten at 0.716.

A reader could reasonably have expected one to imply the other, and the failure is instructive. A repeated question is a question with probability one of a known answer — the extreme case of an uninformative question. Everything between is invisible to the first measurement and visible to the second, and most of the waste lives there.

Stated as a rule: a sort is inefficient when its questions have predictable answers, and repeating a question is only the case where the answer is certain. The information floor is a statement about the second quantity; the first is a special case of it that happens to be much easier to measure.

Heapsort’s line falling is the one worth explaining. Its repeats come from sift-downs comparing two siblings whose order an earlier sift already settled, and the number of such pairs grows with the heap’s shape rather than with the work, so the share shrinks as the array grows. Selection sort’s rises because its redundancy is quadratic and its total is quadratic with a smaller constant.

What this measures and what it does not #

A comparison sort learns about its input only through the comparator, which is what makes both measurements possible and is the same door the adversary who knows the seed uses for a different purpose. Nothing here changes an algorithm; the comparator is replaced and the counts it reports are the counts the algorithm would have made.

Transitivity only. The closure used is the transitive closure of the comparisons made, which is everything a sort can deduce about the order — but a sort may also know things about positions, and a sort that recorded which pairs it had compared could avoid its repeats without any closure at all. The measurement says what is deducible, not what is remembered.

One arrangement per point, except where it is averaged. The share plate is one random arrangement of 256 elements; the bits plate averages 24 arrangements of nine, because counting linear extensions is a walk over $2^n$ subsets and nine is where it stops being free.

A comparison can remove more than one bit on a particular input. The worst-case bound is one bit, against an adversary. On a fixed arrangement a lucky comparison can eliminate more than half the remaining orderings, and random-pivot quicksort averages 0.871 with individual runs above one.

Self-comparisons count as repeats. The median-of-three pivot rule compares a position with itself on a short range, and those are counted as questions whose answer was already known — which is what they are, and which is why its 15.4% is a little above the other quicksorts’ zero.

The hybrid’s row is insertion sort’s row, and for a dull reason. The merge-and-insertion sort reads 0.716 bits over 26.4 comparisons and so does insertion sort, to three figures, because at nine elements the hybrid’s cutoff has not been crossed and it is insertion sort. Its row on that plate is a measurement of the cutoff rather than of the method, and the 256-element plate above is where it says something.

Twenty-four arrangements do not separate two pivot rules. On the bits plate a first-element pivot reads better than a random one — 0.910 against 0.871, or 20.7 comparisons against 22.0 — and over 400 arrangements the order reverses, to 21.5 against 20.2. Twenty-four arrangements of nine elements is ample to rank a quadratic sort against a linearithmic one and nowhere near enough to rank two rules that differ by a few per cent; what randomising the pivot buys is the page that separates them properly, and on average is not a number is why a mean over two dozen draws was never going to.

And the floor is the average-case one. $\log_2 n!$ is the information floor for sorting; two floors that can be added is about a different question with a different floor, and the “times the floor” column here is against the sorting floor throughout.

Still open: the sort that is told what it knows #

Bubble sort with a record of which pairs it had settled would be insertion sort. That is one point on a line, and the line is worth measuring: for each sort, what does it cost to carry the memory that would remove its repeats, and is any of them better off carrying it?

The memory is not free and its price is the interesting part. A bitset of settled pairs is $n^2$ bits, which for 256 elements is 8 KB against the array’s own 2 KB — a structure larger than the data, consulted before every comparison, to avoid comparisons that cost one instruction each. A sort would have to repeat a great many questions before that paid.

The measurement that follows gives each sort that record, counts the comparisons it removes against the bitset reads it adds, and asks where the exchange rate would have to sit for any of them to come out ahead — since a repeated comparison and a bitset lookup are both cheap, and the exchange rate nobody wrote down is the page that had to construct such a rate by hand before it could rank anything. The prediction is that none of them comes out ahead at any rate a real machine offers, which would make redundancy a property worth measuring and not a defect worth fixing.