Theory

Stability as a correctness condition

Radix sort depends on every pass preserving the work of the ones before it. Let us see what happens when one does not.

$ algo radix -in s100k.jsonl
n = 100000, key = Year (1900..2030), 4 passes of base-10 counting sort

inner pass                        comparisons          moves         wall sorted?
stable (backwards)                          0         400000     22.256ms true
UNSTABLE (forwards)                         0         400000      16.21ms false

first break in the unstable run, at index 737:
  1909 1909 1909 1908 1908 1908

Read that table carefully.

Comparisons: 0 and 0. Identical. Moves: 400,000 and 400,000. Identical. Time: comparable. sorted?: true and false.

The same algorithm, the same amount of work, the same data. One character of loop direction — and one result is correct and the other is not.

What the break looks like

1909 1909 1909 1908 1908 1908

The years go down. On the thousands-digit pass every one of these items has the same 1, so that pass had nothing to reorder — only an order to preserve, the one the hundreds, tens and ones passes had built.

The unstable pass reversed it instead. 1908 and 1909, already arranged, swapped places because their thousands digit is equal.

The third and strongest statement of stability

lesson what stability meant
7 a property. Selection sort lacks it — a defect, but it still sorts correctly
8 a consequence. Multi-key ordering collapses; transit's two graphs disagree
9 a correctness condition. Without it the algorithm returns a wrong answer

In lesson 7 an unstable sort still sorted. In lesson 8 it sorted by the key you asked for and destroyed an earlier one. Here it does not sort at all.

Radix sort is not "better with a stable inner pass". It is a stable inner pass, repeated four times. Take the stability away and there is no algorithm left.

Why the test checks both

ncsort_test.go requires RadixSortByYearUnstable to fail to sort, and requires both versions to do the same amount of work. It is the same shape as lessons 7 and 8: the defect is asserted so it stays visible.

If you ever "fix" countingPassUnstable, the test will tell you — and what you will have lost is the demonstration, not gained better code.