Radix Sort | Engineering Interview Kit

Concept

As we saw in the previous section, Counting Sort crashes if the integers are too large (e.g., sorting [1, 9999999] creates an array of 10 Million empty slots).

Radix Sort is the ultimate upgrade to Counting Sort. It retains the blazing fast $O(N)$ non-comparison speed, but completely eliminates the memory explosion problem!

Instead of treating 9999999 as one massive number, Radix Sort looks at the individual digits.
Because a digit in base-10 math can only ever be 0 through 9, Radix Sort only requires exactly 10 empty buckets in memory!

The Mechanism

Radix Sort processes the numbers column by column, usually starting from the least significant digit (the 1s place) and moving leftwards to the most significant digit.

Array: [170, 45, 75, 90, 802, 24, 2, 66]

Pass 1: Sort exclusively by the 1s digit.
We throw them into 10 buckets (0-9) based ONLY on their final digit.

Bucket 0: 170, 90
Bucket 2: 802, 2
Bucket 4: 24
Bucket 5: 45, 75
Bucket 6: 66
Rebuild Array: [170, 90, 802, 2, 24, 45, 75, 66] (It looks chaotic, but the 1s place is perfectly sorted).

Pass 2: Sort exclusively by the 10s digit.
We throw them into the 10 buckets based ONLY on their 10s digit.

Bucket 0: 802, 002
Bucket 2: 024
Bucket 4: 045
Bucket 6: 066
Bucket 7: 170, 075
Bucket 9: 090
Rebuild Array: [802, 2, 24, 45, 66, 170, 75, 90]

Pass 3: Sort exclusively by the 100s digit.
Final Rebuild: [2, 24, 45, 66, 75, 90, 170, 802]
The entire array is flawlessly sorted!

The Stability Requirement

For Radix Sort to mathematically work, the underlying sorting algorithm used to organize the buckets (usually Counting Sort) MUST be Stable.

Why? Look at 170 and 075 during Pass 2 (the 10s column). They both have a 7, so they both land in Bucket 7.
If the sorting algorithm is Unstable, it might spit them out as 075, then 170.
But in Pass 1, 170 was placed before 075 because 0 is smaller than 5! The Unstable sort violently destroyed the hard work of Pass 1!
Because it is a Stable sort, it respects the tie, keeping 170 securely in front of 075, maintaining the mathematical integrity of the lesser digits.

Implementation Details

You will almost never be asked to write a full Radix Sort in an interview because implementing a perfectly stable Counting Sort engine from scratch takes too much boilerplate code.

You just need to understand the Time Complexity.
Time Complexity: $O(W \times N)$
Where $N$ is the number of elements, and $W$ is the maximum “Word Size” (the number of digits in the absolutely largest number).
If the largest number is 999, $W$ is 3. Radix Sort will execute exactly 3 linear passes.

Because $W$ is usually incredibly small (even 1 Billion only has 10 digits), $W$ is treated as a constant, making Radix Sort effectively $O(N)$ .

Interview Questions

Q: Can Radix Sort sort strings alphabetically?
A: Yes! A string is just a sequence of ASCII numbers. Just like you can sort numbers by the 1s digit, 10s digit, and 100s digit, you can sort words by their 3rd letter, 2nd letter, and 1st letter. You just need 26 buckets (A-Z) instead of 10 (0-9). This is highly efficient for sorting millions of string IDs.

Q: If Radix Sort is $O(N)$ and Quick Sort is $O(N \log N)$ , why do languages use Quick Sort by default?
A: Quick Sort is completely generic. if (A < B) works on numbers, floats, strings, and custom user Objects. Radix Sort is strictly mathematical and only works on integer-like representations. Furthermore, Radix Sort carries a heavy constant overhead of constantly moving data in and out of buckets. For small to medium arrays, the raw CPU execution speed of Quick Sort is faster than the heavy bucket manipulation of Radix Sort.