The floor when the values repeat

The comparison-sorting bound rests on counting outputs. There are $n!$ orderings, each comparison distinguishes at most two cases, so no comparison sort finishes in fewer than $\log_2(n!)$ comparisons. It is two lines of argument, exact at every $n$, and matched to within a couple of percent.

The count of outputs is $n!$ only if the keys are distinct.

Take 256 values drawn from eight distinct ones — a column of status codes, a set of grades, a field with a handful of enumerated states. A sorting algorithm cannot tell two equal keys apart and does not need to: every arrangement that produces the same sorted sequence is the same output. The number of outputs it must separate is the multinomial $\binom{256}{k_1, \ldots, k_8}$, and its logarithm is 739 bits against $\log_2(256!) = 1{,}684$.

The real floor is 44% of the quoted one, and every algorithm’s distance from it is more than twice what the usual table reports.

The measurement #

At $n = 256$ with eight distinct values, seeded:

Three separate things are visible in that table and each is worth its own paragraph.

Merge sort is at 1.00 times the permutation floor. On random distinct input it is at 1.03; here it is at 1.00, and at $n = 1{,}024$ it is at 0.99 — genuinely below the number the sorting bound gives. That is not a violation of anything. $\log_2(n!)$ is a worst-case bound over inputs with distinct keys, and this input does not have distinct keys, so the theorem does not apply to it. An algorithm quietly going under a floor is exactly the signal that the floor being used is the wrong one.

Merge sort is at 2.28 times the floor that does apply. It has not become a worse algorithm; the target moved. Merge sort’s structure does not notice repeats — it merges two runs by comparing their heads whether or not the heads are equal — so it spends the same $n \log_2 n$ comparisons it always does, and half of them are now conveying no information.

Every quicksort has got dramatically worse. On random distinct input all three sit near 1.24 times the floor. Here they are at 2.90, 3.14 and 3.40 times the permutation floor and near seven times the real one. Repeated keys are quicksort’s other bad case, and unlike the sorted-input one it is not fixed by the pivot rule — all three rules fail together.

Why two-way partitioning fails on repeats #

The reason is worth spelling out because it is the one bad case of quicksort that randomisation does not touch.

A two-way partition splits the array into “less than the pivot” and “not less than the pivot”. Elements equal to the pivot all go to one side. If eight distinct values are spread over a thousand elements, then whichever value the pivot takes, about an eighth of the array equals it and goes wholesale into one partition — and then gets partitioned again, against a pivot that is very likely the same value, producing the same lopsided split.

The recursion therefore keeps re-partitioning blocks of identical elements that are already in their final relative position, and it does so $\log$-many times over. At $n = 1{,}024$ median-of-three does 71,378 comparisons where merge sort does 8,645: a factor of 8.3, between two algorithms that are within 30% of each other on random input.

The standard fix is three-way partitioning — Dijkstra’s Dutch national flag — which splits into less, equal and greater, and never looks at the equal block again. On an input with $d$ distinct values it turns the cost from $\Theta(n \log n)$ into $\Theta(n \log d)$, which for $d = 8$ and $n = 1{,}024$ is a factor of three and a bit. Every production quicksort has it, and its presence is a decision about this input distribution specifically.

That is the same shape as the insertion-sort cutoff: a universally-implemented modification, justified by a case the headline complexity does not mention, and invisible in every summary of the algorithm.

The floors are further apart at larger n #

At $n = 256$ the two floors differ by a factor of 2.28; at $n = 1{,}024$, by 2.89; at $n = 4{,}096$ the gap keeps widening.

This is not subtle once written down. With $n$ elements over $d$ equally likely values, the permutation floor is about $n\log_2 n - 1.44n$ and the entropy floor is about $n \log_2 d$. The first grows faster than linearly and the second is linear, so the ratio grows like $\log_2 n / \log_2 d$ without bound.

The consequence is that the sorting bound becomes more misleading as the input grows, which is the opposite of the usual direction for an asymptotic statement. Somebody sorting a billion records with a dozen distinct keys is being told a floor that is six or seven times too high.

How few distinct values it takes #

Eight distinct values among 256 is a strong case, and the obvious question is where the effect starts to matter. Sweeping the number of distinct values at $n = 1{,}024$:

The entropy floor is close to $n\log_2 d$ — 1,024 elements over $d$ values need $\log_2 d$ bits each — and the permutation floor is fixed at $n\log_2 n - 1.44n$ regardless. So the ratio is roughly $\log_2 n / \log_2 d$, and it is above two whenever $d < \sqrt{n}$.

That is a low bar. Thirty-two distinct values among a thousand elements already puts the quoted floor 76% too high, and thirty-two distinct values is an enumeration, a rating, a day of the month or a small category. The last row is the reassuring one: drawing 1,024 values uniformly from 1,024 possibilities still produces plenty of collisions — about 37% of the possible values do not appear at all, so a comparable share of those that do appear more than once — and the ratio is nonetheless only 1.05, so the effect really does need the alphabet to be small rather than merely finite.

The right-hand column is the useful one, because it shows what a comparison sort can do about it. Merge sort’s count tracks the entropy floor’s multiple almost exactly: 7.06 at $d = 2$, 2.85 at $d = 8$, 1.07 at $d = 1{,}024$. Its absolute comparison count barely moves — 7,193, 8,229, 8,645, 8,909, 8,939, 8,937 across the whole sweep — because merge sort does not notice repeats at all. It spends $n \log_2 n$ comparisons whatever the alphabet, and the floor falls away beneath it.

An algorithm that did notice would spend $\Theta(n \log d)$, and three-way partitioning is exactly that algorithm. The gap between the two columns is the space that three-way partitioning, counting sort and radix sort occupy, and it is a factor of seven at $d = 2$ and nothing at all at $d = n$.

Where the linear-time sorts come from #

The entropy floor is also the answer to a question the floors field has otherwise had to dodge: how counting sort and radix sort can beat a bound that is supposed to be unbeatable.

They are not comparison sorts, so the decision-tree argument does not constrain them at all — that is the standard answer and it is correct and slightly unsatisfying, because it explains why the theorem does not apply without explaining what they are exploiting.

The entropy floor explains it. Counting sort’s cost on this input is not a comparison count at all; it reads each value once, increments a counter, and writes the output: 256 reads and 264 writes, 520 operations in total, against merge sort’s 1,682 comparisons and 3,364 reads. It never distinguishes two equal keys because it never compares anything, and its cost is proportional to $n + d$ rather than to either floor.

So the honest statement is not “counting sort breaks the bound”. It is:

• the permutation floor, 1,684 bits, describes a problem this input does not pose;
• the entropy floor, 739 bits, describes the information that must be extracted;
• a comparison sort extracts it one bit at a time and needs at least 739 comparisons;
• an algorithm allowed to look at the values extracts all of it in one pass, because reading an 8-valued key yields three bits rather than one.

The floor moves when the operation moves, which is the floors field’s recurring result arriving from a new direction. Every previous instance changed the question; this one changes what a step is allowed to be.

The floor in bits, which is where radix sort lives #

There is one more floor under both of the ones above, and naming it completes the picture.

An algorithm that may look at the bits of a key is not bounded by the number of comparisons at all; it is bounded by how many bits it must read. Sorting $n$ keys of $b$ bits requires reading $nb$ bits in the worst case, because a key never read cannot be placed. That is the input-size floor, and it is the analogue of the adversary bound for connectivity — a coverage argument rather than a counting one.

Radix sort achieves it to within a constant. It reads each key once per digit, and with $b$ bits taken $r$ at a time that is $b/r$ passes over $n$ elements. For 32-bit keys and 8-bit digits, four passes: $4n$ reads and $4n$ writes, whatever $n$ is.

Set the three floors side by side for 1,024 keys drawn from eight values:

The bottom two are nearly equal, and that is not a coincidence — with $d$ equally likely values the entropy is $n\log_2 d$ and the minimum key width is $\lceil\log_2 d\rceil$ bits, so the two agree whenever $d$ is a power of two. The information a sort must extract and the information it must read are the same information.

Which is the cleanest way to see why the linear-time sorts are not cheating. They are not getting under a floor; they are operating against a different and lower floor, they reach it, and the reason the comparison sorts cannot is that a comparison yields one bit where a digit read yields $r$.

The gap between the two floors is not a fact about one size. It widens with $n$ at a fixed number of distinct values, because $\log_2 n!$ grows faster than the multinomial does, and two more points of the sweep say so.

What the gate does with this #

Two assertions, and the second is the one that would catch a mistake.

The two floors must be far apart. With eight distinct values among 256, the entropy floor must be under half the permutation floor. If the input generator were changed so that repeats became rare, this figure would be comparing two nearly-identical lines and its whole argument would evaporate — silently, with a perfectly reasonable-looking picture.

At least one algorithm must sit on the permutation floor. Merge sort at 1.00 is the evidence that the quoted bound is the wrong one: an algorithm exactly at a floor, on an input where a better algorithm exists, means the floor is not binding. If merge sort ever drifted to 1.3 the figure would still draw and the essay’s opening claim would be unsupported.

There is also a check that does not appear here and appears everywhere else in this field. The main floor figure asserts that nothing averages below the floor, which is the assertion that catches an instrument that has stopped counting. It cannot be used on this input, because on this input going below $\log_2(n!)$ is correct behaviour and merge sort does it at $n = 1{,}024$.

Losing an assertion is a real cost and it is the reason this is a separate essay with a separate figure rather than an option on the existing one. A gate that has to be disabled for one case is a gate with a hole in it; a second figure with its own two assertions is not.

Skew makes it worse, and real data is skewed #

Every measurement above uses eight values that occur about equally often, and that is the kindest case for the quoted floor. The multinomial’s logarithm is $n H$, where $H$ is the entropy of the value distribution, and $H$ is at its largest when the values are equally likely. Make them unequal and the floor falls further.

Take the shape a real column actually has. A status field where 99% of rows are ok and the remaining one per cent is spread over seven other codes has an entropy of about 0.11 bits per element. At $n = 1{,}024$ that is a floor of a hundred and twelve bits.

The quoted floor is seventy-eight times the one that applies, and merge sort — which does not look at values and spends about 8,900 comparisons whatever the input contains — is eighty times above the information it is extracting.

That is not an exotic instance. It is what a status column, an error code, a boolean flag with a rare true, a category with a dominant member, or any log line’s severity field looks like. The distribution that makes the standard bound most misleading is the distribution real data most often has, and it is misleading in the direction that flatters every algorithm measured against it.

It also says which algorithms would notice. Three-way partitioning collapses the dominant value into a single equal block in one pass, so it does very well here; a run-detecting merge sort finds the long stretches of the dominant value as ready-made runs and merges them cheaply. Both are exploiting skew rather than merely tolerating repeats, and the difference between the two rows above is exactly the size of the prize.

The floor a comparison sort can reach, and the one it cannot #

Three-way partitioning is offered above as the fix, and it is worth being precise about which floor it reaches, because it is not the one in the table.

A three-way quicksort on $n$ elements over $d$ distinct values costs $\Theta(n \log d)$. When the values are equally likely that is the entropy floor up to a constant, since $H = \log_2 d$ exactly, and the algorithm is optimal in the sense that matters.

When they are not equally likely, $H$ is strictly less than $\log_2 d$ — 0.11 against 3.00 in the table above — and $\Theta(n\log d)$ is no longer close to $nH$. The algorithm’s cost depends on how many distinct values there are and the floor depends on how they are distributed, and the two come apart exactly when the distribution is skewed.

Closing that last gap needs an algorithm whose comparison count is governed by the frequencies rather than by the count of distinct values, and there is one: sort by merging the runs of equal elements in a Huffman-shaped merge tree, so that the frequent values are merged at shallow depth and the rare ones deep. The total is $nH + O(n)$ comparisons, which is the floor.

That construction is the coding field’s tree, used for a different purpose. A Huffman code assigns short codes to frequent symbols and its expected length is within a bit of the entropy; here the same tree assigns shallow merges to frequent values and its comparison count is within a constant of the same entropy. Sorting a multiset optimally and coding it optimally are the same problem, and the identical tree solves both — which is worth knowing chiefly because it says the floor in this essay is not a curiosity but the same quantity the compression field has been measuring all along.

It is named here and not built. What is measured on this page is where the floors are; which algorithm reaches which of them is a claim about implementations, and the only one this collection has measured is that the algorithms it holds reach none of them on this input.

What to take from it #

The general lesson is not about repeated keys. It is that a lower bound is a statement about a set of inputs, and the set is usually named so casually that it disappears.

$\log_2(n!)$ is quoted as “the sorting bound”. It is the bound for sorting $n$ distinct keys by comparison, and the word “distinct” is doing as much work as the word “comparison” — which at least gets stated, because the exception to it is famous.

Real data is full of repeats. A sorted column of timestamps at second resolution, a list of countries, an enumeration, a floating-point field rounded for display: all of these have $d \ll n$, and for all of them the quoted floor overstates the unavoidable work by a factor that grows with the size of the data. An algorithm chosen because it comes within 2% of a floor is coming within 2% of the wrong floor.