Introduction

Radix sort is a non-comparison sorting algorithm that orders values by processing their digits one position at a time. Instead of asking whether one element is less than another, it groups elements by digit buckets and relies on stable passes to build the final sorted order.

The Core Idea

Suppose you want to sort these integers:

170, 45, 75, 90, 802, 24, 2, 66

In least-significant-digit radix sort, you first group numbers by the ones digit, then by the tens digit, then by the hundreds digit, and so on. The earlier passes still matter because each pass must be stable: elements with the same current digit keep the order established by previous passes.

That stability is what makes the whole algorithm work.

LSD Radix Sort Step by Step

For base 10 integers, each pass looks at one decimal digit.

1. Sort by ones digit.
2. Sort the result by tens digit.
3. Sort the result by hundreds digit.
4. Continue until the most significant digit of the largest number is processed.

After the ones-digit pass, the example becomes ordered by last digit. After the tens-digit pass, it is ordered by the last two digits. After the hundreds-digit pass, the whole list is sorted.

A Runnable Python Example

A common implementation uses counting sort as the stable subroutine for each digit:

1def counting_sort_by_digit(values, exp):
2    output = [0] * len(values)
3    count = [0] * 10
4
5    for value in values:
6        digit = (value // exp) % 10
7        count[digit] += 1
8
9    for i in range(1, 10):
10        count[i] += count[i - 1]
11
12    for value in reversed(values):
13        digit = (value // exp) % 10
14        output[count[digit] - 1] = value
15        count[digit] -= 1
16
17    return output
18
19
20def radix_sort(values):
21    if not values:
22        return values
23
24    result = list(values)
25    exp = 1
26    maximum = max(result)
27
28    while maximum // exp > 0:
29        result = counting_sort_by_digit(result, exp)
30        exp *= 10
31
32    return result
33
34
35numbers = [170, 45, 75, 90, 802, 24, 2, 66]
36print(radix_sort(numbers))

This prints:

[2, 24, 45, 66, 75, 90, 170, 802]

Why It Can Be Fast

If there are d digit positions and n items, radix sort typically runs in O(d * (n + b)), where b is the bucket count or radix. For fixed-size integers and a fixed radix, that is often close to linear in practice.

That is why radix sort can outperform comparison sorts on certain structured inputs, especially when keys are fixed-width integers or strings.

However, the algorithm is not universally superior. It needs extra memory, and its usefulness depends heavily on the shape of the data.

Stability Is Not Optional

The stable inner sort is the subtle but crucial part. If the per-digit sort were unstable, the ordering established by earlier digits would be destroyed, and the final result could be wrong.

So radix sort is really a strategy plus a requirement:

• strategy: sort one digit position at a time
• requirement: use a stable pass for each position

Common Pitfalls

One common mistake is forgetting that the inner digit sort must be stable. That breaks the algorithm even if each digit pass looks locally correct.

Another issue is assuming radix sort is always best. For general-purpose sorting of arbitrary objects, comparison sorts are often simpler and more flexible.

It is also easy to ignore special cases such as negative numbers, variable-length strings, or very large alphabets. A basic integer-only implementation does not automatically handle those well.

Summary

• Radix sort orders data by processing digits one position at a time.
• Least-significant-digit radix sort relies on stable sorting for each digit pass.
• A common implementation uses counting sort as the stable inner routine.
• Its time complexity is often O(d * (n + b)), which can be very efficient for fixed-width keys.
• The algorithm works best when the key structure is known and digit-based processing is practical.