Quick reference
Complexity | |
---|---|
Worst case time | |
Best case time | |
Average case time | |
Space |
Strengths:
- Linear Time. Radix sort takes time to sort n 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 list.
Complexity
Radix sort takes time and space, where n is the number of items to sort, \ell 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 \ell digits in the input numbers, and counting sort has a time complexity of .
The space complexity also comes from counting sort, which requires space to hold the counts, indices, and output lists.
In many implementations, including ours, we assume that the input consists of 64-bit integers. This means that the number of digits, \ell 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 time and space.
Interview coming up?
Get the free 7-day email crash course. You'll learn how to think algorithmically, so you can break down tricky coding interview questions.
No prior computer science training necessary—we'll get you up to speed quickly, skipping all the overly academic stuff.
No spam. One-click unsubscribe whenever.
You're in! Head over to your email inbox right now to read day one!