Radix Sort
Radix sort is a non-comparison-based sorting algorithm that sorts integers by processing individual digits from the least significant to the most significa...
Digit-by-Digit Sorting
Radix sort is a non-comparison-based sorting algorithm that sorts integers by processing individual digits from the least significant to the most significant (LSD radix sort) or from most significant to least significant (MSD radix sort). By using counting sort as a stable subroutine on each digit, radix sort can sort n integers with d digits each in O(d times n) time.
The key insight is stability. When counting sort is used to sort by the least significant digit, numbers with the same ones digit maintain their relative order from the input. When we then sort by the tens digit, numbers with the same tens digit maintain the relative order established by the ones-digit sort. After sorting by every digit from least to most significant, the entire array is sorted correctly.
A worked example: sort the array 170, 45, 75, 90, 802, 24, 2, 66 using LSD radix sort with base 10. First pass (ones digit): group by ones digit to get 170, 90, 802, 2, 24, 45, 75, 66. Second pass (tens digit): group by tens digit to get 802, 2, 24, 45, 66, 170, 75, 90. Third pass (hundreds digit): group by hundreds digit to get 2, 24, 45, 66, 75, 90, 170, 802. The array is now sorted.
Time complexity is O(d times (n plus k)) where d is the number of digits and k is the base (radix). For fixed-size integers (say 32-bit integers with base 256 giving d equals 4 passes), this simplifies to O(n). Space complexity is O(n plus k) for the counting sort auxiliary arrays.
Radix sort outperforms comparison sorts when d is small and n is large. For 32-bit integers, d is at most 4 with a base of 256, making radix sort O(4n) which beats O(n log n) for sufficiently large n.
Interview tip: when asked about the fastest way to sort a million 32-bit integers, the answer is radix sort or counting sort, not merge sort or quick sort. Demonstrating knowledge of non-comparison sorts for large datasets with bounded values is a strong signal of algorithmic breadth.
LSD vs MSD Radix Sort
The two main variants of radix sort differ in which end of the number they process first, and each variant has distinct characteristics that make it more suitable for different applications.
LSD radix sort processes the least significant digit first. It always processes all d digits for every element regardless of the actual values, making it a batch algorithm well-suited for fixed-length keys such as 32-bit or 64-bit integers. LSD radix sort is naturally iterative, requiring d passes over the entire array. Each pass uses counting sort, which is cache-friendly because it scans the array sequentially. LSD radix sort is stable by construction.
MSD radix sort processes the most significant digit first. After sorting by the first digit, elements are partitioned into groups (one per digit value) and each group is sorted recursively by the next digit. MSD radix sort can short-circuit: if a group has only one element, it is already sorted and no further passes are needed for that group. This makes MSD radix sort adaptive and often faster on inputs where the data naturally clusters by leading digits.
MSD radix sort can also sort variable-length strings naturally, while LSD radix sort requires padding strings to equal length. For lexicographic sorting of strings, MSD radix sort is generally preferred.
A worked example comparing the two: sort 10,000 customer IDs, most of which start with the prefix 10 or 20. MSD radix sort partitions the data into two large groups after the first pass and recurses within each group, finishing quickly because elements within each group have few distinct remaining digits. LSD radix sort processes all four digits for every element regardless, doing more unnecessary work.
Time complexity: LSD O(d times (n plus k)), MSD O(d times n) in the best case with early termination. Space complexity: LSD O(n plus k), MSD O(n plus k) per level, O(d times (n plus k)) total in the worst case for recursion.
Interview tip: distinguish LSD from MSD by noting that LSD is simpler, cache-friendly, and iterative, while MSD is adaptive, handles variable-length keys, and is better for string sorting. Use this distinction to match the variant to the specific problem.
Choosing the Right Base
The base (radix) chosen for radix sort has a direct impact on performance, and selecting the optimal base is an important practical consideration. Larger bases reduce the number of passes but increase the size of the count array. Smaller bases require more passes but use less memory per pass.
For 32-bit integers, the choice of base is typically 256 (one byte). With base 256, each 32-bit integer has exactly 4 digits (bytes), so radix sort makes exactly 4 passes. Each pass uses a count array of size 256, which fits easily in CPU cache. This combination of few passes and cache-friendly count arrays makes base-256 radix sort extremely fast in practice.
Using base 10 on the same 32-bit integers would require up to 10 passes (since 32-bit integers can have up to 10 decimal digits) and use a count array of size 10. The passes are more numerous but each count array fits in cache even more easily. In practice, base 256 is faster because the reduced number of passes outweighs the slightly larger count array.
Using base 65536 (16 bits) for 32-bit integers would require only 2 passes but a count array of 65,536 entries, which is 256 kilobytes for 32-bit count values. This exceeds L1 cache size on most processors, causing cache misses during the count array updates that negate the benefit of fewer passes.
The optimal base is approximately the square root of the maximum value for integers, or one byte for fixed-size integers, as a practical rule of thumb.
A worked example of the performance difference: sorting 10 million 32-bit integers. Base-256 radix sort with 4 passes outperforms comparison sorts for arrays larger than roughly 1 million elements on modern hardware. Below this threshold, the cache-friendly access patterns of quick sort often win.
Time complexity with optimal base b and d digit positions: O(d times (n plus b)) equals O(n) when d and b are constants. Space: O(n plus b).
Interview tip: when implementing radix sort in an interview, default to base 256 for integers and explain that it balances the number of passes against the count array size to maximize cache utilization.