Radix Sort
Radix Sort is a non-comparative sorting algorithm. It avoids comparison by creating and distributing elements into buckets according to their radix. For elements with more than one significant digit, this bucketing process is repeated for each digit, while preserving the ordering of the prior step, until all digits have been considered.
1. The Core Concept
Unlike Merge Sort or Quick Sort, Radix Sort does not compare numbers against each other (a > b). Instead, it exploits the fact that information about the size of a number is encoded in the number of digits and the value of those digits.
- Radix: The base of the number system (e.g., 10 for decimal, 2 for binary).
- Buckets: We need 10 buckets (0-9) for decimal numbers.
2. How it Works (LSD - Least Significant Digit)
The most common variation is LSD Radix Sort. It processes the digits from right to left (ones place, tens place, hundreds place...).
Example: [170, 45, 75, 90, 802, 24, 2, 66]
- Sort by Ones:
170, 90, 802, 2, 24, 45, 75, 66
- Sort by Tens:
802, 2, 24, 45, 66, 170, 75, 90(Note: 802 has 0 in tens, 2 is 02)
- Sort by Hundreds:
2, 24, 45, 66, 75, 90, 170, 802
Crucial: The sorting of each digit must be Stable (e.g., using Counting Sort). If sorting by tens destroys the order established by the ones, the algorithm fails.
3. Complexity
- Time Complexity: $O(nk)$
- $n$: Number of elements.
- $k$: Number of digits in the largest number.
- Space Complexity: $O(n + k)$
If $k$ is small (numbers are not huge), Radix Sort can be faster than $O(n \log n)$ comparison sorts. However, if numbers are distinct and large ($k \approx \log n$), it degrades to $O(n \log n)$.
4. The Subroutine: Counting Sort
Radix sort relies on a stable sorting algorithm to sort the digits at each place value. Counting Sort is typically used because it is extremely efficient ($O(n+k)$) for small ranges of integers (like digits 0-9).
- How it works: It counts the occurrences of each digit and uses those counts to determine the position of each element in the output array.
- Stability: Crucially, the implementation of Counting Sort used in Radix Sort must be stable. This means if two numbers have the same digit at the current place value (e.g.,
12and32when sorting by ones), their relative order from the previous iteration must be preserved.
5. Implementation (Python)
def counting_sort(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
# Store count of occurrences in count[]
for i in range(0, n):
index = (arr[i] // exp)
count[index % 10] += 1
# Change count[i] so that count[i] now contains actual
# position of this digit in output array
for i in range(1, 10):
count[i] += count[i - 1]
# Build the output array
i = n - 1
while i >= 0:
index = (arr[i] // exp)
output[count[index % 10] - 1] = arr[i]
count[index % 10] -= 1
i -= 1
# Copy the output array to arr[], so that arr now
# contains sorted numbers according to current digit
for i in range(0, n):
arr[i] = output[i]
def radix_sort(arr):
# Find the maximum number to know number of digits
max1 = max(arr)
# Do counting sort for every digit. Note that instead
# of passing digit number, exp is passed. exp is 10^i
# where i is current digit number
exp = 1
while max1 // exp > 0:
counting_sort(arr, exp)
exp *= 105. Pros and Cons
| Pros | Cons |
|---|---|
| Fast: Can be faster than QuickSort for integers. | Limited: Only works for integers or fixed-length strings (data must be mappable to digits). |
| Stable: Preserves order of equal elements. | Space: Requires extra space for buckets. |
| Non-Comparative: Doesn't rely on comparison operators. | Cache: Not as cache-friendly as QuickSort. |