Radix Sort Algorithm

Strengths & Weaknesses

Strengths:

• Linear Time. Radix sort takes O(n)O(n) time to sort nn integers with a fixed number of bits.
• Punch card Friendly. Way back in the day (like the 50's and 60's), programs were written on these cards with holes in them, called punch cards. ↴ Radix sort works really well for sorting these physical cards. (It was a big deal at the time.)

Weaknesses:

• Restricted inputs. Radix sort only works when sorting numbers with a fixed number of digits. It won't work for arbitrarily-large numbers.

How It Works

Radix sort works by sorting the input numbers one digit at a time. As an example, let's sort this list:

First, we'll sort on the one's place:

Any stable sorting algorithm can be used here. In practice, counting sort works well, since the digits can only take on a small number of values (i.e.: 0 - 9 for base-10 numbers; 0 - 1 for base-2 numbers).

Here's what sorting on the one's place gets us:

Then, we'll sort on the ten's place:

Notice how whenever there was a tie in the tens place the number with a lower ones digit came first. This is why using a stable sorting algorithm is important. It means that if there's a tie on the current digit we'll fall back to how the numbers were ordered based on the digits we already sorted.

And finally, we'll sort on the hundred's place:

Once we've sorted all the digits, we're done! :)

Implementation

Here's how we'd code it up. We'll assume that all the inputs are 64-bit integers.

Since the numbers are stored in binary, we'll run our radix sort on their binary digits (instead of the digits in their base-10 representations).

We'll be using bit shifting and bitwise ands ↴ to extract individual bits from items in the input array.

Radix Sort - Java Implementation

Radix Sort - Python Implementation

Complexity

Radix sort takes O(ℓ∗(n+k)) time and O(n+k) space, where n is the number of items to sort, ℓ is the number of digits in each item, and k is the number of values each digit can have.

This time complexity comes from the fact that we're calling counting sort one time for each of the ℓ digits in the input numbers, and counting sort has a time complexity of O(n+k).

The space complexity also comes from counting sort, which requires O(n+k) space to hold the counts, indices, and output arrays.

In many implementations, including ours, we assume that the input consists of 64-bit integers. This means that the number of digits, ℓ is a constant (64). With a binary number, each digit can either be a zero or a one, meaning that k is also a constant (2). With these assumptions, radix sort becomes O(n) time and O(n) space.

Reference:

https://www.interviewcake.com/concept/python/radix-sort