Loading...
Radix Sort sorts integers one digit at a time — least-significant digit first — using a stable counting sort for each digit position. With d digits and base b it runs in O(d·(n + b)), effectively linear for fixed-width integers, and is widely used for sorting large sets of numbers or fixed-length strings.
Sorts digit by digit using a stable counting pass per digit.
| Average case | O(n·k) |
| Worst case | O(n·k) |
| Space | O(n + k) |
| Stable | Yes |
Complexities are for the reference implementation shown; constant factors and cache behavior vary by language.
Idiomatic, copy-paste implementations. Pick your language:
Python
def radix_sort(arr):
if not arr:
return arr
max_val = max(arr)
exp = 1
while max_val // exp > 0:
counting_by_digit(arr, exp)
exp *= 10
return arr
def counting_by_digit(arr, exp):
n = len(arr)
output = [0] * n
counts = [0] * 10
for x in arr:
counts[(x // exp) % 10] += 1
for d in range(1, 10):
counts[d] += counts[d - 1]
for x in reversed(arr): # stable: iterate right to left
d = (x // exp) % 10
counts[d] -= 1
output[counts[d]] = x
arr[:] = outputSorting [23, 1, 45, 12] step by step:
The control flow of the algorithm as a diagram: