Part II · Radix sorts · week 5

Key-indexed counting

Count how many keys have each value, turn the counts into starting positions, then place every key directly where it belongs. Linear, and stable.

Run the animation, step by step → generated live from any input you type — nothing is pre-recorded

Cost and properties

time	O(n + R)
compares	zero
stable	yes — and that is the point
space	n + R

Reference: Sedgewick & Wayne, §5.1.

Key-indexed counting in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

def key_indexed_counting(a, R):
    # a[i] is a small integer key in [0, R). No key is ever COMPARED with
    # another -- the key's value is used directly as an array index.
    n = len(a)
    count = [0] * (R + 1)
    for i in range(n):                    # 1. count frequencies (offset 1)
        count[a[i] + 1] += 1
    for r in range(R):                    # 2. cumulate -> starting index
        count[r + 1] += count[r]
    aux = [None] * n
    for i in range(n):                    # 3. distribute, left to right
        aux[count[a[i]]] = a[i]           #    -> STABLE
        count[a[i]] += 1
    for i in range(n):                    # 4. copy back
        a[i] = aux[i]
    return a

Why it works

The offset-by-one trick

count[a[i] + 1] += 1 writes the frequency of key r into count[r+1]. After cumulating, count[r] holds the index where the first key equal to r goes — exactly what the distribution pass needs. Counting into count[r] instead forces an awkward second shift; the offset makes the cumulate come out right by construction.

Why it is stable

The distribution pass walks the input left to right and, for each key, increments its counter after placing it. So among equal keys the earlier one is placed first and lands earlier. Walk the input backwards and it is still a correct sort but no longer stable — and then LSD radix sort, which is built on this stability, breaks.

Beating n log n

n log n is a lower bound for sorts that compare keys. This one never compares: it uses the key as an address. The catch is in the assumption — keys must be small integers, and the cost includes R, so counting-sorting 64-bit integers would need 2⁶⁴ counters. Change the model, escape the bound; the fine print is where the honesty lives.

Where it is used

As the inner loop of LSD and MSD radix sorts, in suffix-array construction, in BWT/bzip2, and anywhere keys are naturally bounded — sorting a million records by day of week, US area code, DNA base, or exam grade.

What to try in the animation

R is taken as one more than the largest key. Every key must be a small non-negative integer — that restriction is what buys linear time.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

twelve keys — 3 1 4 1 5 2 0 3 2 4 1 0
few distinct values — 1 0 1 0 1 0 1 0 1 0
already sorted — 0 1 2 3 4 5
one big value — 0 1 0 1 9

Open Key-indexed counting in the player →

The rest of Radix sorts

LSD radix sort Sort by the last character, then the one before it, and so on.
MSD radix sort Sort on the first character, then recur inside each group.