Why sorting cannot get faster
Sorting a hundred things needs at least 525 comparisons. Not with today's algorithms. Ever.
Most claims about performance are claims about a particular program. This one is not. It says that no comparison-based sorting algorithm, written by anyone, in any language, on any hardware that has not yet been invented, can sort a hundred items in fewer than 525 comparisons.
The argument never looks at an algorithm.
Count the destinations, not the steps
A list of n distinct items can be arranged in n! orders. Exactly one of them is sorted, and before you start you have no idea which one you are holding.
Now consider what a comparison gives you. You ask whether a comes before b and you get back yes or no. One bit. Whatever your algorithm does next, it does it knowing one binary fact more than before.
So after c comparisons you have received c bits, and c bits can distinguish at most 2c different situations. To be certain of identifying which of the n! arrangements you started with, you need
2c ≥ n!, that is, c ≥ log₂(n!).
That is the whole proof. It contains no loops, no recursion and no assumptions about strategy, which is precisely why it applies to algorithms nobody has thought of yet.
The standard name for it is the decision-tree bound. Picture any comparison sort as a tree: each internal node is a comparison, each branch is one of the two answers, and each leaf is a possible arrangement. A tree of depth c has at most 2c leaves, and the tree must have at least n! of them, so its depth is at least log₂(n!). Depth is the worst-case number of comparisons.
What the numbers actually are
Twelve items can be arranged 479,001,600 ways. The logarithm of that is 28.84, so twelve items need at least 29 comparisons. A hundred items need at least 525. A million need at least 18,488,885.
Open the Big-O Complexity Explorer and read the row for N = 100. The O(N log N) column says 664, sitting between O(N) at 100 and O(N²) at 10,000. That 664 is N × log₂N, the growth rate we call optimal for sorting.
But the floor is 525, and 664 is 26.6% above it.
The gap is not sloppiness in the tool. log₂(n!) is not quite n log₂ n: Stirling's approximation gives n log₂ n − 1.4427n, and at N = 100 that correction is worth 139 comparisons. So "N log N" names the right shape while overstating the true cost by a constant factor of the input size. The shape is what survives as N grows; the 139 is what you would notice if you actually counted.
The exit that is not a loophole
Counting sort will sort a million small integers in far fewer than 18 million operations, and it does not contradict a word of the above.
The proof assumes every question you ask is a comparison. Counting sort asks a different kind of question: it reads a key and uses it as an address. That extracts far more than one bit at a time, because it exploits something the comparison model refuses to assume, namely that the keys are small integers you are allowed to look inside.
This is the useful habit. A lower bound is always a lower bound within a model, and when a result seems to have been beaten, the model was changed. Sorting Race runs the comparison-based algorithms against each other, and what separates them is constant factors and memory behaviour, not the exponent. They are all bounded below by the same 525.
Where you have met this before
If the counting move feels familiar, it is the one behind why no compressor can shrink every file. There the count was of possible files against possible shorter files; here it is of possible arrangements against possible answer sequences. Both proofs work by noticing that a set of outcomes is larger than the set of things that could describe them.
Entropy Coding is the same quantity from the other direction: the number of bits you genuinely need is set by how many possibilities remain, and no encoding beats it.
Neither result tells you how to write a fast program. They tell you when to stop looking for one.
References (1)
- minimum-comparison sorting Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, §5.3.1.