The limits of sorting

Mergesort's worst case is $n \log_{2} n - n + 1$ comparisons, which is close enough to $n \log_{2} n$ to raise the question of whether anything can do better.

That question has an answer, and it is unusual in this course because it is a statement about every possible algorithm rather than about one. It says that a whole family of sorts is stuck where mergesort already is, and it says exactly why. Then it points at the escape, which is to stop being a member of that family.

What a comparison sort is allowed to know

Every sort so far, selection, insertion, bubble, merge and quicksort, learns about the input in exactly one way: it picks two elements and asks which is smaller. It never looks at a key's value, never does arithmetic on it, never uses it as an address. Such an algorithm is a comparison sort, and the restriction is not artificial: it is what lets one sorting routine work on integers, strings, dates and user-defined records alike, given only a comparison function.

Fix $n$ and consider all the ways the input could be arranged. If the elements are distinct there are $n!$ arrangements, and each one requires a different sequence of moves to put right. The algorithm must produce the right permutation for every one of them, and the only information it ever receives is the yes-or-no answers to its comparisons.

So the run of the algorithm on any particular input is a path through a decision tree. Each internal node is a comparison, "is $a_{i} < a_{j}$ ?", with two branches. Each leaf is the point at which the algorithm stops and outputs an ordering. Two inputs that give the same answers to every comparison follow the same path and reach the same leaf, so they get the same output. If those two inputs needed different outputs, the algorithm is wrong on at least one of them.

That is the entire argument in one sentence: a correct comparison sort needs at least $n!$ distinct leaves, one for each permutation it might have to undo.

Counting the depth

A binary tree of height $h$ has at most $2^{h}$ leaves, because each level at most doubles the count. Needing $L$ leaves therefore forces $h \geq \log_{2} L$ . With $L = n!$ ,

h \geq \log_{2} (n!)

and $h$ is the number of comparisons made on the longest path, which is the worst case. So no comparison sort, existing or yet to be invented, can sort $n$ elements in fewer than $\log_{2} (n!)$ comparisons in the worst case.

Now put a size on $\log_{2} (n!)$ . Stirling's approximation gives $n! \approx \sqrt{2 π n} (n / e)^{n}$ , and taking logarithms,

\log_{2} (n!) = n \log_{2} n - n \log_{2} e + {\frac{12}{\log}}_{2} (2 π n) + \dots

Since $\log_{2} e = 1.4427$ , the bound is $n \log_{2} n - 1.4427 n$ plus a term that grows only logarithmically. For a million elements that is 19,931,569 minus 1,442,695, so about 18,488,900 comparisons. Mergesort's worst case on the same input is 18,931,570. Mergesort is within 2.4 per cent of a bound that applies to every comparison sort that will ever be written. There is nothing significant left to win.

Example. What is the smallest number of comparisons that could possibly sort five elements, and is it achievable?

There are $5! = 120$ orderings, and $\log_{2} 120 = 6.907$ , so at least seven comparisons are needed, since a comparison count is a whole number. Seven is achievable: the merge insertion algorithm of Ford and Johnson (1959) sorts five elements in seven comparisons, and so does the more ordinary route of sorting the first two, inserting the third by binary search, and continuing. So the bound is tight here.

Now you. How many comparisons are needed at minimum for eight elements, and for ten?

Answer

$8! = 40 {,} 320$ and $\log_{2} 40 {,} 320 = 15.30$ , so at least 16. $10! = 3 {,} 628 {,} 800$ and $\log_{2}$ of that is 21.79, so at least 22. Both bounds happen to be achievable, at 16 and 22 respectively, but that is a fact about small numbers rather than a consequence of the argument.

What the bound does not say

The result is often quoted as "sorting is $n \log n$ ", which is wrong in three separate ways, and each of them matters.

It is not exact. The counting argument gives a floor, not a construction, and the floor is sometimes unreachable. For twelve elements $\log_{2} (12!) = 28.84$ , so the bound says 29, yet Mark Wells showed by exhaustive search in 1965 that 30 comparisons are genuinely required and 29 is impossible. The information count says how much has to be learned; it does not promise that comparisons can be arranged to learn it that efficiently.

It bounds comparisons, not time. An algorithm making the minimum number of comparisons can still be slow, because comparisons are not the only cost. Mergesort and quicksort make comparison counts within 40 per cent of each other and differ in running time by more, in quicksort's favour, entirely through data movement and memory access. A count of comparisons is a good proxy, not the thing itself.

It bounds the worst case over all inputs, which leaves the door open for inputs that are not arbitrary. If the array is already sorted, insertion sort finishes in $n - 1$ comparisons, far below $\log_{2} (n!)$ , and there is no contradiction: that algorithm still needs a deep tree for the inputs it has not been given. Adaptive sorts exploit exactly this. Timsort, which ships in Python and in Java for objects, finds runs that are already ordered and merges them, so it costs $Θ (n)$ on sorted or reverse-sorted input and $Θ (n \log n)$ at worst.

The average case is bounded too, and by essentially the same amount. The average number of comparisons is the average leaf depth of the tree, and a binary tree with $n!$ leaves has average depth at least $\log_{2} (n!)$ minus a constant. So a comparison sort cannot be fast on average either. Randomising the input does not help; the bound holds regardless.

Not comparing

Every step of the argument used the assumption that the algorithm's only access to the data is through comparisons. Break that assumption and the bound simply does not apply.

Suppose the keys are integers from 0 to $k - 1$ . Then a key can be used as an array index, and indexing is not a comparison. Counting sort does this. Make an array $C$ of $k$ counters. Sweep the input once, incrementing $C [x]$ for each key $x$ . Replace $C$ by its running totals, so that $C [v]$ holds the number of keys less than or equal to $v$ , which is the position just past where the last $v$ belongs. Then sweep the input backwards, placing each key at position $C [x] - 1$ and decrementing $C [x]$ .

The cost is $Θ (n + k)$ : two passes over $n$ elements and one over $k$ counters. When $k$ is comparable to $n$ this is linear, and it beats every comparison sort by a factor of $\log n$ . The backwards final sweep is what makes it stable, which is the property the next algorithm depends on entirely.

The catch is $k$ . Sorting a million 32-bit integers this way needs $2^{32}$ counters, sixteen gigabytes, to sort four megabytes of data. Counting sort is for small key ranges: exam marks, ages, bytes, priority levels.

Example. Counting-sort the marks 3, 1, 4, 1, 5, 0, 2, 3, 1, 4, where marks run from 0 to 5. Show the counters and the total work.

Counts: 0 appears once, 1 three times, 2 once, 3 twice, 4 twice, 5 once, so $C = [1, 3, 1, 2, 2, 1]$ . Running totals: $C = [1, 4, 5, 7, 9, 10]$ . Reading those, the single 0 goes to position 0, the three 1s to positions 1 to 3, the 2 to position 4, and so on, giving 0, 1, 1, 1, 2, 3, 3, 4, 4, 5. The work is $n + k = 10 + 6 = 16$ operations, against the 22 comparisons that the counting bound says any comparison sort needs for ten elements.

Now you. Counting-sort 2, 5, 3, 0, 2, 3, 0, 3 over the same range 0 to 5.

Answer

Counts $C = [2, 0, 2, 3, 0, 1]$ , running totals $C = [2, 2, 4, 7, 7, 8]$ , output 0, 0, 2, 2, 3, 3, 3, 5. Work is $8 + 6 = 14$ . Note that the counter for 1 is zero and for 4 is zero, and the algorithm pays for them anyway: the $k$ in $Θ (n + k)$ is the width of the range, not the number of distinct keys present.

Radix sort

Counting sort is cheap when the key range is small, and a wide key can be cut into small pieces. That is radix sort: treat each key as a sequence of $d$ digits in base $r$ , and counting-sort by each digit in turn, least significant first.

It works only because counting sort is stable. After sorting by the units digit, records with equal units digits are in their original relative order; sorting by the tens digit preserves that order among equal tens digits, so ties in the tens are broken by the units, which are already right. By induction, after the pass on digit $i$ the array is correctly sorted on the low $i + 1$ digits. Use an unstable sort for a pass and the result is garbage.

Example. Radix-sort 458, 921, 305, 174, 638, 920, 057 by hand, one decimal digit per pass.

By units digit: 920, 921, 174, 305, 057, 458, 638. By tens digit, stably: 305, 920, 921, 638, 057, 458, 174. By hundreds digit: 057, 174, 305, 458, 638, 920, 921, which is sorted. Three passes over seven elements, 21 placements and no comparisons at all.

Now you. Radix-sort 213, 902, 130, 921, 013, 900 the same way.

Answer

Units: 130, 900, 921, 902, 213, 013. Tens: 900, 902, 213, 013, 921, 130. Hundreds: 013, 130, 213, 900, 902, 921. Watch 900 and 902 at the second pass: both have tens digit 0, and they keep the relative order the first pass gave them, which is what leaves them correct at the end.

The total cost is $Θ (d (n + r))$ for $d$ passes over $n$ elements with $r$ counters each. The choice of $r$ is a real optimisation. To sort a million 32-bit keys, an 8-bit digit gives $d = 4$ and a cost of $4 (10^{6} + 256) \approx 4.0 \times 10^{6}$ ; an 11-bit digit gives $d = 3$ and $3.0 \times 10^{6}$ ; a 16-bit digit gives $d = 2$ and $2.1 \times 10^{6}$ ; a 20-bit digit still gives $d = 2$ but a million counters, pushing the cost back up to $4.1 \times 10^{6}$ . Sixteen bits wins, and the shape of that calculation, cost falling with wider digits until the counter array starts to dominate, is the whole of the tuning.

That is between four and nine times fewer operations than the 18.5 million comparisons a comparison sort needs. In practice the margin is smaller than the operation count suggests, because each pass writes elements to scattered positions and misses the cache, whereas quicksort's inner loop is a sequential scan. Radix sort wins on large arrays of fixed-width numeric keys and loses on small ones.

Bucket sort, and the assumption it hides

The third non-comparison sort assumes something about the distribution rather than the range. Bucket sort divides the key space into $n$ equal intervals, drops each key into the bucket its value selects, sorts each bucket with insertion sort, and concatenates.

If the keys are independent and uniform over the interval, the expected number in a bucket is 1, and the expected total cost of the insertion sorts is $Θ (n)$ , giving a linear-time sort. If they are not uniform, the analysis evaporates: put every key in one bucket and the cost is the quadratic cost of insertion-sorting all of them. Bucket sort is a statement about the input, and it is only as reliable as that statement.

That is the honest summary of this whole section. Counting sort requires a small range, radix sort requires fixed-width keys and pays in cache misses, bucket sort requires a distribution. None of them defeats the counting argument, because none of them is a comparison sort, and none of them is a general-purpose replacement for one.

Where sorting ends

Sorting is now finished as a topic, and it leaves behind a result the rest of the course will keep using: an array can be put in order for $Θ (n \log n)$ , after which any element can be found in $Θ (\log n)$ by binary search.

That is a good deal, and it has one weakness. Sorting is a batch operation on a fixed array. Insert one new key into a sorted array and the shifting costs $Θ (n)$ , so a collection that changes while being searched pays linear time per update, and the $\log n$ lookup is bought with a cost that dwarfs it.

The next lesson attacks the lookup rather than the ordering. It asks whether $Θ (\log n)$ is really necessary to find a key, or whether a key could be made to compute the address where it lives, and answers in constant time on average. What that costs is order itself: the structure that results cannot tell you what the next largest key is, or list its contents in sequence, at any price.