The Speed Limit of Sorting

No sort that learns about its input only by comparing two items can beat about n log n comparisons, with the logarithm in base 2. That is not an observation about the sorts people have found so far. It is a limit on every sort anyone could ever write in that style, and the argument for it fits on a napkin.

The limit binds comparisons, not sorting. Counting sort and radix sort never compare two items. They look inside the keys instead and finish in a fixed number of linear passes, at the price of knowing exactly what the keys are.

Sorting as Twenty Questions

Here is the argument, in a form short enough to repeat to a colleague. Three items can arrive in six different orders, and n items in n factorial orders: n times n minus one times n minus two, down to one. A sort must tell every one of those orders apart, because each needs a different set of moves to fix. If two different orders led the sort through the same questions, it would make the same moves on both and get one of them wrong.

Every comparison is a yes-or-no question, "is a smaller than b?", and the best any single answer can do is rule out half of the orders still possible. Starting from n factorial possibilities and halving at best each time, the sort needs at least the base-2 logarithm of n factorial questions before one order is left. The proof ends there.

For three items there are six orders, and a tree of yes-or-no questions with six leaves must be at least three questions deep somewhere, because two questions can separate only four cases. For 10 items there are 3,628,800 orders, which need at least 22 questions. For a million items the logarithm of a million factorial is about 18.5 million, which is n times the logarithm of n, about 19.9 million, less a small correction. So a comparison sort of a million items needs about 18.5 million comparisons in its worst case. CPython's sort on a million random numbers measured 18.6 million.

What the Limit Says and Does Not Say

The limit holds for the worst case, and it also holds for the average over all possible orders: most orders sit deep in the tree, so the typical input cannot do much better than the worst. And it counts comparisons only.

It does not stop an adaptive sort from finishing already sorted input in n minus one comparisons, which Sorting in the Real World shows CPython's sort doing. Sorted input is one order out of n factorial, one leaf that the sort reaches quickly by checking for it first; the limit is about all the leaves together. And it says nothing at all about sorts that never compare two items.

Counting Sort

When the keys are small integers, there is no need to compare anything. Count how many items carry each key in one pass. Turn the counts into starting positions with a running total: the 1s start at position 0, the 2s start after all the 1s, and so on. Then place every item at its key's next free position in a second pass.

Sorting 2 million library records by publication year over a 3,000-year span takes two passes over the records and an array of 3,000 counters, with no comparisons at all. The cost is O(n + k) for n items and a key range of k. Because the second pass walks the input in order and appends each item behind the earlier items with the same key, counting sort is stable, and that property is what makes radix sort work.

Radix Sort

Radix sort handles keys too wide for one counting array by sorting on one digit at a time, least significant digit first, with a stable counting sort for each digit. A 32-bit integer is four 8-bit digits, so a million 32-bit keys take four passes, each with 256 counters: about 4 million placements, where a comparison sort of the same million makes about 20 million comparisons.

Stability is what keeps it correct. After the units pass, numbers are in order by their last digit. The tens pass sorts by the tens digit, and because it is stable, numbers with equal tens digits keep the units order from the pass before. After the last pass the whole key is in order. With an unstable pass the earlier digits' work would be thrown away.

The Price of Stepping Around

Counting sort costs memory proportional to the key range. A 32-bit key would need about 4 billion counters, which is why radix sort splits keys into digits. Radix sort in turn needs keys that break into digits whose order is the key's order. Integers do, and so do fixed-width byte strings. A custom ordering does not: case-insensitive text, or titles ordered by the collation rules of a language.

And each pass scatters its writes across 256 destinations, jumping around memory the way the cache punishes (Chapter 4), so on an ordinary processor a good comparison sort often keeps up with radix sort in practice. GPUs, with thousands of threads counting in parallel, are where radix sort dominates; NVIDIA's CUB library, for one, provides a device-wide radix sort (Chapter 3).

What the Limit Costs Day to Day

A million keys cost about 20 million comparisons whichever comparison sort the library picks, so the part of the cost still negotiable is the price of each comparison. In Python, a key function runs once per item, n times, and the sort then compares cheap precomputed values. A comparison function, which Python 3 accepts only after wrapping it with functools.cmp_to_key, runs once per comparison as a full Python call.

Measured on Python 3.15, sorting a million random integers called a key function 1,000,000 times and a wrapped comparison function 18,621,174 times, and the comparison-function sort took 2.7 seconds against 0.2 for the plain sort. The cheapest sort of all is the one that never runs, because an index kept the data in order as it was written, the B-tree of Chapter 6.