Radix sort explained: how it works, code and complexity

What problem radix sort solves

Counting sort is linear but needs a count array as large as the whole key range, which is impossible for 32-bit or 64-bit integers. Radix sort splits each key into small digits and runs counting sort once per digit, so each pass needs a count array of only b entries (10 for decimal digits, 256 for bytes).

It works for any key that can be broken into a fixed sequence of small symbols: non-negative integers, dates written as YYYYMMDD, fixed-length codes such as postal codes, IP addresses and fixed-width strings.

Worked example: LSD radix sort in base 10

Sort [170, 45, 75, 90, 802, 24, 2, 66]. The largest number has 3 digits, so there are 3 passes. Each pass is a stable sort by one digit: equal digits keep the order from the previous pass.

After pass 2, numbers are sorted by their last two digits. In pass 3, 2, 24, 45, 66, 75 and 90 all have hundreds digit 0, and stability keeps them in the order pass 2 produced. That is why each pass must be stable.

Python implementation

def counting_pass(nums, exp, base):
    """Stable counting sort of nums by the digit at exp."""
    count = [0] * base
    for x in nums:
        count[(x // exp) % base] += 1
    for d in range(1, base):
        count[d] += count[d - 1]
    out = [0] * len(nums)
    for x in reversed(nums):
        d = (x // exp) % base
        count[d] -= 1
        out[count[d]] = x
    return out

def radix_sort(nums, base=10):
    """LSD radix sort for non-negative integers."""
    if not nums:
        return []
    exp, biggest = 1, max(nums)
    while biggest // exp > 0:
        nums = counting_pass(nums, exp, base)
        exp *= base
    return nums

print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]
print(radix_sort([3, 0, 1, 0], base=256))   # [0, 0, 1, 3]

Using base 256 means each pass looks at one byte, so 32-bit integers need only 4 passes. To include negative numbers, sort the negative and non-negative values separately and join them, or offset all keys by the minimum. For fixed-length strings, use the character code at position i as the digit and go from the last position to the first.

Time and space complexity

When d is a constant (fixed-width keys) and b is chosen near n or a fixed value such as 256, the time is O(n). For n keys that are all distinct, d must be at least log_b n, so radix sort does not beat O(n log n) for arbitrary-size keys; it is fast because each step is a simple array operation.

How radix sort compares with other sorts

In the table, n is the number of keys, k the key range for counting sort, d the number of digits and b the base. LSD radix sort is stable as long as every digit pass is stable. It needs keys with a fixed structure, while comparison sorts such as merge sort and quicksort work with any ordering, including custom comparison functions.

LSD vs MSD, and common mistakes

When to use radix sort

Radix sort is a good fit for large arrays of fixed-width integers or keys, such as 32-bit IDs, timestamps, IPv4 addresses or fixed-length strings, especially on GPUs and in high-performance libraries where its regular memory access pays off. It is used in suffix-array construction and in some database and graphics workloads. For ordinary Python lists, sorted() is almost always faster in practice because it runs in optimized C code. In interviews, radix sort comes up when asked how to sort in linear time, for example the Maximum Gap problem.