This page walks through radix sort end to end: why a sequence of stable single-digit sorts produces a fully sorted array, how each counting pass works internally, how to extend the basic integer version to negative numbers and fixed-length strings, and when the linear-time bound actually beats a well-tuned O(n log n) comparison sort in practice.
Radix sort is a non-comparison sort that processes integer keys digit by digit, using a stable bucket sort at each digit. It runs in O(n·k) time where k is the number of digits — linear in n for fixed-width keys.
| Best | Average | Worst | Space (Worst) |
|---|---|---|---|
Ω(nk) |
Θ(nk) |
O(nk) |
O(n+k) |
LSD (least-significant-digit) radix sort: for each digit position from the lowest to the highest, distribute keys into 10 (or 256) buckets by that digit, then collect them back in order. Because each digit pass is stable, prior digits' order is preserved and the whole sequence ends up sorted.
def radix_sort(arr):
"""LSD radix sort for non-negative integers."""
if not arr:
return arr
max_val = max(arr)
exp = 1
out = list(arr)
while max_val // exp > 0:
out = _counting_pass(out, exp)
exp *= 10
return out
def _counting_pass(arr, exp):
n = len(arr)
out = [0] * n
count = [0] * 10
for x in arr:
count[(x // exp) % 10] += 1
for i in range(1, 10):
count[i] += count[i - 1]
for i in range(n - 1, -1, -1):
digit = (arr[i] // exp) % 10
count[digit] -= 1
out[count[digit]] = arr[i]
return out
print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))The trace above sorts the classic textbook input. In pass 1 the keys are grouped only by their ones digit: 170, 90, 802 and 2 end in 0 or 2 and move to the front, while 66 ends in 6 and moves to the back. Pass 2 groups by the tens digit; 802 and 2 both have a tens digit of 0, and because the pass is stable, 802 stays ahead of 2 exactly as pass 1 left them. Pass 3 groups by the hundreds digit and resolves the remaining order. After three passes (the number of digits in the largest key, 802) the array is sorted. The invariant is that after pass i the array is sorted with respect to the lowest i digits; stability is what carries that invariant forward.
Each pass is a counting sort keyed on a single digit. The first loop builds a histogram of how many keys have each digit value. A prefix sum turns the histogram into end positions: after it, count[d] is the index just past the last slot for digit d. The scatter loop walks the input from right to left and decrements the slot before writing, which is what makes the pass stable. Walking left to right with decrement would reverse equal keys and break the algorithm. The work per pass is O(n + b) where b is the base, so the full sort is O(k(n + b)) for k digits.
Choosing the base is a tuning knob. Base 10 is easy to read but wastes work; production implementations usually use base 256 (one byte per pass) so a 32-bit integer needs only four passes and the count array still fits in L1 cache. Base 65536 halves the passes again but the count array gets large and cache misses dominate.
LSD radix sort, shown above, always performs k full passes over the data regardless of the input. MSD radix sort starts from the most significant digit, partitions keys into buckets, and recursively sorts each bucket on the next digit. MSD can stop early once a bucket has one element or all keys are exhausted, which makes it a good fit for variable-length strings where most keys differ in the first few characters. It is not naturally stable, and it recurses, so small buckets are usually handed off to insertion sort.
The basic implementation only handles non-negative integers. Negative numbers can be handled by splitting the input, or more efficiently by offsetting every key by the minimum value. Fixed-length strings sort with the same LSD loop by treating each character position as a digit with base 256.
def radix_sort_signed(arr):
"""LSD radix sort that also handles negative integers."""
if not arr:
return []
lo = min(arr)
shifted = [x - lo for x in arr] # all keys now >= 0
exp, out, hi = 1, shifted, max(shifted)
while hi // exp > 0:
buckets = [[] for _ in range(10)]
for x in out:
buckets[(x // exp) % 10].append(x) # append keeps it stable
out = [x for b in buckets for x in b]
exp *= 10
return [x + lo for x in out]
def radix_sort_strings(words, width):
"""LSD sort of equal-length ASCII strings."""
for pos in range(width - 1, -1, -1):
buckets = [[] for _ in range(256)]
for w in words:
buckets[ord(w[pos])].append(w)
words = [w for b in buckets for w in b]
return words
print(radix_sort_signed([-5, 3, -12, 0, 8, -1])) # [-12, -5, -1, 0, 3, 8]
print(radix_sort_strings(["dab", "cab", "fad", "bad", "dad"], 3))The bucket-list version trades the counting arrays for Python lists. It is easier to read and still stable, because append preserves arrival order inside each bucket. For large numeric arrays in Python, NumPy's np.sort(kind="stable") uses radix sort internally for small integer dtypes, which is far faster than any pure-Python loop.
| Situation | Radix sort | Comparison sort |
|---|---|---|
| Millions of 32-bit or 64-bit integer keys | Good: 4 to 8 byte passes | O(n log n), branchy comparisons |
| Fixed-length strings, IP addresses, dates | Good | Fine |
| Small arrays (under a few hundred items) | Overhead of count arrays dominates | Better (insertion sort, Timsort) |
| Arbitrary objects with a custom comparator | Not applicable | Required |
| Floating-point keys | Possible with a bit-twiddling key transform | Simpler |
Radix sort is used in GPU sorting libraries, database engines for sorting fixed-width keys, and suffix-array construction. On a general-purpose CPU with modest n, a good comparison sort is often just as fast, because radix sort's scattered writes are cache-unfriendly.