Radix Sort

Radix sort orders integers digit by digit using a stable counting sort per digit, achieving linear time when the key width is bounded.

Sorting without comparing

Radix sort does not compare whole keys. Instead it sorts by one digit at a time, most commonly from the least significant digit up. Each pass distributes the numbers into buckets by the current digit using a stable sort, then collects them back. Because each pass is stable, order established by earlier, less significant digits is preserved.

Why least-significant-digit works

After sorting by the ones digit, then the tens digit, and so on, the final pass on the most significant digit produces fully sorted output. The stability of each pass is essential: it ensures ties on the current digit keep the order set by lower digits.

• Time: O(d(n + b)) for d digits, base b, n keys
• Linear O(n) when d and b are treated as constants
• Extra space: O(n + b)
• Stable: yes; comparison-free

Beating the comparison bound

Comparison sorts cannot beat O(n log n), but radix sort is not a comparison sort, so it sidesteps that lower bound. When keys are fixed-width integers or strings and d is small, radix sort runs in effectively linear time. The catch is that d and the base b hide in the constant, so it only wins when keys are short relative to n.

def counting_by_digit(a, exp):
    out = [0]*len(a)
    count = [0]*10
    for x in a: count[(x//exp) % 10] += 1
    for i in range(1, 10): count[i] += count[i-1]
    for x in reversed(a):
        d = (x//exp) % 10
        count[d] -= 1
        out[count[d]] = x
    return out

Where it is used

Radix sort suits large volumes of fixed-width keys: integer IDs, fixed-length strings, and sort keys in databases. It also underlies fast sorting on GPUs, where its regular memory access pattern parallelises well. For general-purpose comparison of arbitrary objects, a comparison sort remains the right choice.