A key too wide for one counting sort can be split into d digits in base b and sorted one digit at a time, least significant first, each pass a stable counting sort over b buckets. The cost is Θ(d(n + b)), and the reason the passes compose into a sorted array is not arithmetic: it is that every pass leaves its own ties in the order the pass before it produced.
Core ideas
The hard idea is the invariant across passes, and it is where a reader's intuition about significance runs exactly backwards.
That is the invariant, and it is what has to be preserved. Pass d puts the keys in order of digit d. Two keys that agree in digit d are left in the order the previous pass gave them, which by the invariant was order on digits 0 … d−1. So they come out ordered on digits 0 … d, which is the invariant again one digit wider. After the last pass the array is sorted on the whole key.
The step above used exactly one property of the pass: that it leaves its ties alone. Take it away and the argument has nothing. The lab supplies a variant whose passes reverse their buckets, and on the standard seven keys the result is 355 329 457 436 657 720 839 — not sorted, and the pass that broke it is any of them.
Running the digits from the most significant down feels right and is wrong unless each bucket is then sorted recursively. Without that, the final pass is the one on the units digit and it rearranges the whole array, so everything the earlier passes arranged is overwritten. The lab's output is 720 355 436 457 657 329 839, whose units digits read 0 5 6 7 7 9 9: sorted on the least significant digit and on nothing else.
The material
The passes, the invariant that makes them compose, and the two variants the lab lets you watch fail.
Least-significant-digit radix sort sorts n keys, each of d digits in base b, by performing d passes. Pass i is a stable counting sort of the whole array on digit i, counting digits from the least significant, which is digit zero. After the last pass the array is sorted.
Each pass is counting sort with k = b, so a pass costs n + b and the whole sort costs d(n + b). Nothing is compared, so the comparison lower bound is as silent here as it was there: on seven keys it says 13 comparisons are necessary for any comparison sort, and this algorithm makes none.
The keys are 329 457 657 839 436 720 355. Three passes, 17 units of work each, 51 in all. Pass one reads the units digit, pass two the tens, pass three the hundreds, and the array after each pass is in the worked example below. Only after the third pass is it sorted, and after the first two it is sorted on a suffix of the key.
If every pass is a stable sort on its digit, then after the pass on digit i the array is in increasing order of the number formed by digits 0 through i of each key.
By induction on i. Before any pass, the claim is about no digits at all and holds vacuously.
Suppose it holds after the pass on digit i−1, and run a stable pass on digit i. Take two keys x and y with x before y in the output. If their digits i differ, the pass placed them in increasing order of that digit, and digit i outranks all the digits below it, so the numbers formed by digits 0 … i are in increasing order.
If their digits i agree, the pass left them in the order it found them, which by the inductive hypothesis was increasing order of digits 0 … i−1. Since their digits i are equal, that is increasing order of digits 0 … i as well. The claim holds after pass i, and after pass d−1 it is the whole key.
□
Read the second paragraph of that proof again: the only fact used about the pass was stability, and it was used in the case where the current digit decides nothing. That is why an unstable pass does not merely degrade the result — it removes the argument entirely, and the lab shows the array that comes out.
The base is free and it moves both terms. Larger b means fewer digits d = ⌈log_b U⌉ for keys below U, and a bigger bucket array per pass. The same seven keys cost 3 × (7 + 10) = 51 in base ten, 10 × (7 + 2) = 90 in base two, and 3 × (7 + 16) = 69 in base sixteen. There is no rule that one base always wins; there is a product to evaluate, and the lab evaluates it as you move the control.
The honest form of the cost is therefore Θ(d(n + b)) with d depending on the key width and the base, which is why radix sort is not Θ(n) in any useful sense. For n keys drawn from 0 … n^c − 1 and base b = n, it is Θ(cn), and that statement carries its hypotheses in it.
Unstable passes, least significant first: 355 329 457 436 657 720 839 — not sorted. Most significant first with no recursion: 720 355 436 457 657 329 839 — not sorted, and sorted on the units digit alone, because the pass that ran last read the units. The lab checks both against the sorted array rather than asserting failure.
Neither variant is a strawman. The first is what happens when the per-digit sort is replaced by something convenient that happens not to be stable. The second is what happens when a reader reasons from significance: the most important digit should be settled first. Most-significant-digit radix sort is a real and useful algorithm — it recurses into each bucket, which is precisely the step whose absence the lab is demonstrating.
Interactive
One counting sort per digit, and two ways to break the composition
Method
The check between passes is the whole discipline: after pass i the array is sorted on a suffix of the key, and you can verify that.
d = ⌈log_b U⌉ where U bounds the keys. Write down d(n + b) before running anything, and compare it with the same product at another base. This is the sizing step, and it is the one that decides whether radix sort is worth the bucket array.
Bucket by the least significant digit, and inside each bucket keep the input order. Concatenating the buckets in order gives the array after pass one.
After pass i, the array must be in order of the last i + 1 digits of each key. This is checkable by eye on seven keys and it is how you find the pass that went wrong, rather than discovering at the end that the output is not sorted.
In the base-ten example, the third pass leaves 329 before 355 because both have hundreds digit 3 and the second pass had already put them in that order. That single observation is the correctness proof in miniature; if you can see it once you will not run the passes in the other order.
Switch the variant to unstable passes and then to most-significant-first, and read the outputs. The second one is the more instructive: the array comes out ordered by its units digit, which is the signature of the last pass having overwritten everything.
The keys are the lab's defaults. Each pass buckets the whole array by one digit, keeping the order inside each bucket, and concatenates the buckets from digit zero upwards.
The load-bearing line is bucket 3 of pass three. It holds 329 and 355, which agree in the hundreds digit, and it holds them in that order because pass two put 329 before 355 and pass three did not disturb its own ties. Every correctly ordered pair of keys that agree in the hundreds digit is there for the same reason.
Notice also what pass one and pass two produced: arrays that are not sorted and are not meant to be. After pass one the array is in order of units digits; after pass two, in order of the two-digit number formed by tens and units, which you can read off as 20 29 36 39 55 57 57. The invariant is checkable at every stage.
For a faded rehearsal, set the base to 2 and predict two things before looking: the number of passes, and the total work. The supplied first move is that 839 needs ten binary digits, so d = 10; work out d(n + b) and then check it, and say which of base 2, 10 and 16 you would choose for these seven keys and why the answer would change for seven million of them.
You should be able to run three digit passes by hand, verify after each one that the array is sorted on the digits seen so far, compute d(n + b) at two bases, and explain both failure modes from the induction rather than from the output.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.