Iteration

Radix Sort

Radix Sort is another sorting algorithm that can run faster than $O(n \log n)$ because it's not a comparison sort algorithm. It only works on integers. Unlike Counting Sort, it avoids the O(maxval - minval) cost.

You can assume you're sorting nonnegative integers here for simplicity.

First Few Test Cases:

There are two variants of Radix Sort: LSD and MSD. First, we'll go over LSD, and then MSD.

LSD is really the DP/bottom-up solution, and MSD is the recursive/top-down solution.

Least Significant Digit (LSD) Radix

LSD Radix is when you sort all numbers by their last digit, then 2nd-to-last digit, etc. At the end, surprisingly your numbers are all sorted.

\notag \text{Initial numbers:} \ \ \ [22, 30, 06, 03, 21]

\notag \text{Sort by last digit:} \ \ \ [30, 21, 22, 03, 06]

\notag \text{Then by 2nd-to-last:} \ \ \ [03, 06, 21, 22, 30] \ \ \ \text{(sorted!)}

People usually use a version of Counting Sort to do the sorting here, but any stable sorting algorithm will do. It's just important the relative order doesn't change if there's a tie.

Here's the modified counting sort we used:

To see why this works, consider what happens to the 22 and 21. The 1s digit number first gets sorted, so the 21 is definitely to the left of the 22, with some random other numbers possibly in-between. Later when we sort by the bigger digit they'll be placed together. Since it's a stable sort, the 21 is kept to the left of the 22.

Time Complexity $O((n + b) \cdot D)$ , where $D$ is the number of digits and $b$ is the base (here, base 10). Counting Sort runs in $O(n + \max - \min)$ time, we run it $D$ times, and the value of $\max - \min$ is $b$ . You usually pick a base less than $n$ so sometimes $b$ is omitted.

Space Complexity $O(n\cdot D)$ . This is the space used for stringifiedNums, and the same thing for each individual Counting Sort. If $D$ is fixed, this is essentially $O(n)$ .

Notes

Notice that the number 10 takes 2 digits to write. The number 100 takes 3 digits to write, and the number 1000 takes 4 digits. In general, to represent a number $N$ , the number of digits $D$ it takes to write it is $\log_b N$ , where $b$ is the base (base 10 here).

We can rewrite the time complexity as $O(n \cdot log_b N)$ time, where $N$ is the largest number in the numbers we want to sort. We used base 10 above, but people will pick a base $b$ that minimizes their time complexity:

\notag \text{Time Complexity: }{O((n+b)\cdot \log_bN)}

Most Significant Digit (MSD) Radix

MSD Radix Sorting is the recursive version of this algorithm which we'll derive now. Instead of going right-to-left, it goes left-to-right. It can be faster because it can stop dynamically e.g. when a bucket is empty, but its call stack takes up extra space.

The idea behind the recursion is that sorting an array of numbers is the same as as grouping all the numbers together by their most significant digit, and then doing the same on those numbers' next-most significant digit, and so on.

For example, if we start with [22, 30, 06, 03, 21], then we first group and sort by leftmost digit [0{3, 1}, 2{2, 1}, 3{3}], and then the next digit, and keep going until there are no more digits left [01, 03, 21, 22, 33].

Here's the recursion for this:

1. Recursion

2. Base case

When there are no more digits to look at, we should just end.

3. Code

Here's the full code, putting together recursion and base case.

Time Complexity $O((n+b) \cdot D)$ , where $n$ is the number of elements and $D$ is the length of numbers being sorted. If $D$ is fixed, e.g. you're working with 32-bit integers, this is essentially $O(n+b)$ .

Space Complexity $O(n \cdot D)$

When to use Radix

The classic rule of thumb for Radix is sorting a large number of fixed-size integers, like 10 million entries of 32- or 64-bit integers, because Counting Sort would take O(2^32) time or O(4.2 billion), MergeSort would take O(10 million * 23), and Radix Sorting can be made to take O(10 million * 4) with $b=256$ . Radix can also be chunked in memory more easily than Counting Sort when you get to working with huge $n$ , but this is getting off topic from an interview.

Mark as Completed:

Submits:

radixSort

Test your code to get an output here!

radixSort(

)

Test your code to get an output here!