Counting sort

Three passes, no comparisons.

CountingSortByRating(items):
    k ← MaxRating - MinRating + 1
    count ← array of k zeroes

    // 1. Count how many times each rating occurs.
    for each it in items:
        count[it.Rating - MinRating] += 1

    // 2. Prefix sums: count[v] becomes the index ONE PAST v's last
    //    position in the output.
    for i from 1 to k-1:
        count[i] += count[i-1]

    // 3. Place them. BACKWARDS — and that is what makes it stable.
    out ← array of len(items)
    for i from len(items)-1 down to 0:
        v ← items[i].Rating - MinRating
        count[v] -= 1
        out[count[v]] ← items[i]
        moves.Hit()
    return out

Read the third pass again. There is not a single comparison between two items. The key names the position directly.

The complexity is O(n + k): n for the passes over the data, k for the prefix sums.

Why backwards

The prefix sum gives the position of the last element with that value. Going from the end, the last item lands in the last slot of its block, the one before it in the one before, and the original order survives.

Go forwards and equal items come out reversed. One change of loop direction and stability is gone. Step 6 shows that this is not a detail.

Radix sort

Counting sort needs an array of size k. For Year that is 131 — fine. But what if the key were a full int64?

Radix sort sidesteps that: it sorts one digit at a time, and for a single digit k is only 10.

RadixSortByYear(items):
    out ← copy of items
    for d from 0 to 3:                 // ones, tens, hundreds, thousands
        out ← countingPass(out, d)     // a stable counting sort
    return out

Least significant digit first. Four passes instead of one, but each with ten buckets instead of 131.

And this is where stability becomes load-bearing

When you sort by the tens digit, the ones digit is already in order. The second pass must preserve that — otherwise the first pass's work is gone.

Preserving it is exactly what a stable sort does.

In lesson 7 stability was a property. In lesson 8 it was a consequence. Here it is a correctness condition: without it, radix sort is not untidy — it is wrong.

Step 6 shows that as two numbers and one false.