LSD Radix Sort

LSD radix sort sorts keys by scanning digit positions from right to left, starting with the least significant digit. Each pass uses a stable sorting method on one digit position.

The usual inner method is stable counting sort. Stability is essential because later passes must preserve the order already established by earlier, less significant digits.

Problem

Given $n$ keys of fixed width $m$ , where each digit is in range $[0, b)$ , sort the keys in increasing order.

A key has the form:

x = d_{m-1}d_{m-2}\cdots d_1d_0

LSD radix sort processes:

d_0, d_1, \ldots, d_{m-1}

Algorithm

lsd_radix_sort(A, m, b):
    for p from 0 to m - 1:
        stable_counting_sort_by_digit(A, p, b)

    return A

Example

Sort:

[329, 457, 657, 839, 436, 720, 355]

After ones digit:

[720, 355, 436, 457, 657, 329, 839]

After tens digit:

[720, 329, 436, 839, 355, 457, 657]

After hundreds digit:

[329, 355, 436, 457, 657, 720, 839]

Correctness

After pass $p$ , the array is sorted by the suffix of digits:

d_p d_{p-1}\cdots d_0

The base case holds after sorting by $d_0$ . For the induction step, stable sorting by $d_p$ groups elements by the new digit while preserving the order of lower digits inside each group. Therefore the array becomes sorted by digits $d_p$ through $d_0$ .

After the final pass, every digit has been considered, so the array is sorted by the full key.

Complexity

Each digit pass costs:

O(n + b)

For $m$ digit positions, total time is:

O(m(n + b))

Space:

O(n + b)

For fixed width integers and a fixed byte base, this is linear in $n$ .

When to Use

Use LSD radix sort when:

keys have fixed width
digit extraction is cheap
stable counting sort is available
the digit alphabet is small
sorting many integers or fixed length strings

It is less natural for variable length strings unless they are padded or handled with a sentinel digit.

Implementation

def lsd_radix_sort(a, digits, base=10):
    for p in range(digits):
        a = counting_sort_digit(a, p, base)
    return a

def counting_sort_digit(a, p, base):
    count = [0] * base
    divisor = base ** p

    for x in a:
        digit = (x // divisor) % base
        count[digit] += 1

    for i in range(1, base):
        count[i] += count[i - 1]

    out = [0] * len(a)

    for i in range(len(a) - 1, -1, -1):
        x = a[i]
        digit = (x // divisor) % base
        count[digit] -= 1
        out[count[digit]] = x

    return out