# LSD Radix Sort

# 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

```text id="l2g6qx"
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

```python id="7q9nmx"
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
```