Radix Sort
Sorts digit by digit into buckets, without any direct value comparisons.
- Comparisons 0
- Swaps 0
- sorted indices 0
- compare
- swap
- sorted
Pseudocode
1 max = max(a); exp = 1
2 while max / exp > 0
3 countingSortByDigit(exp)
4 exp *= 10
5
6 countingSortByDigit(exp):
7 count[0..9] = 0
8 for i from 0 to n - 1: count[digit(a[i], exp)]++
9 for d from 1 to 9: count[d] += count[d - 1]
10 output = new array of size n
11 for i from n - 1 downto 0
12 d = digit(a[i], exp)
13 output[count[d] - 1] = a[i]; count[d]--
14 copy output to a
Step log
How it works, runtime and memory
Radix Sort sorts numbers digit by digit, never comparing values directly. The LSD variant (Least Significant Digit) starts at the least significant digit: it distributes elements into 10 buckets (digits 0–9 in base 10) and gathers them back in bucket order. This step repeats for each digit until the most significant one. Because the per-digit distribution is stable, every iteration preserves the order of equal keys, and after the last digit the array is correctly sorted. Runtime is O(d · (n + b)) where d is the digit count of the largest element and b is the base (10 here); for integers with known magnitude d is constant, so Radix Sort runs effectively linearly. Memory is O(n + b) for the buckets and the algorithm is stable. Applicable only to nonnegative integers or data with a fixed digit structure.
Complexity
- Best case
O(d · n) - Average case
O(d · n) - Worst case
O(d · n) - Extra space
O(n + b)
When to use it
Sorting large amounts of integer keys with bounded digit count, such as phone numbers, postal codes or IPv4 addresses. Also found in database engines and in string sorting as the MSD variant.