Counting and radix sort

When the values are whole numbers in a small range, you can sort without comparing at all. Count how many times each value appears, then write them out in order. This runs in linear time.

Counting sort

Suppose every value is a whole number from 0 to k − 1. Make a list of k counters. One pass over the input counts each value. Then go through the counters in order and write each value as many times as it was counted.

When every value is a whole number from 0 to k − 1, make a list count of k zeros. One pass over the input adds 1 to count[v] for each value v. A second pass goes through v = 0, 1, …, k − 1 and writes each v out count[v] times. Writing it is SORT-P5.

One pass of n and one pass of k: O(n + k) time and O(k) extra space for the counters. When k is no bigger than about n, that is O(n). When k is huge, for example values up to a billion, the counter list is the problem, and a comparison sort is better.

A stable version, for records

Real data is usually records sorted by a key, such as trains by platform number. Writing out “the value v, count[v] times” loses the records. Instead, turn the counts into starting positions, then place each record:

def counting_sort_by(recs, key, k):
    count = [0] * k
    for r in recs:
        count[key(r)] += 1
    start = [0] * k                   # where each key's block begins
    for v in range(1, k):
        start[v] = start[v - 1] + count[v - 1]
    out = [None] * len(recs)
    for r in recs:                    # in input order: stable
        out[start[key(r)]] = r
        start[key(r)] += 1
    return out

start is a prefix sum of the counts (ARRS-4). Records are placed in the order they arrive, so records with equal keys keep their order. The sort is stable, which radix sort depends on.

Radix sort

Numbers up to a billion are too spread out for one counting sort. But each digit is only 0 to 9. Radix sort sorts by the last digit, then by the one before it, and so on, with a stable counting sort each time. Step through the second version of the figure.

Why it works: after sorting by the last t digits, the list is in order of those t digits. The next pass sorts by digit t + 1. Values that tie on that digit keep their order from before, because the pass is stable, so they stay ordered by their last t digits. By induction, after all d passes the list is sorted.

Cost: d passes of O(n + b), where b is the base (10 for decimal digits). Using base 2¹⁶ (16 twos multiplied together, 65,536) for 32-bit numbers needs only 2 passes.

Now try SORT-P5, Passenger ages.