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]))