What’s a Radix Sort?
Many of the sorting algorithms you may first encounter have relatively self-explanatory names once you understand their inner workings - Bubble, Insertion, Merge Sort and so on..
What is a ‘Radix’ though?
A short trip over to Wikipedia tells us:
“In a positional numeral system, the radix or base is the number of unique digits, including the digit zero, used to represent numbers.”
Not much clearer, but let’s return in a bit.
How is Radix Sort different?
Bubble, Insertion and Merge Sort mentioned earlier are all examples of comparison algorithms. That is, they rely on comparing elements in the collection being sorted to determine their correct position.
Radix Sort is a non-comparitive algorithm - none of the elements being sorted are compared against one another.
How does Radix Sort work?
Radix Sort works by placing numbers into different ‘buckets’ depending on the value of the digits.
The buckets are for each ‘Radix’ or ‘Base’ of the number - If we are working with base 10 numbers - we can have buckets for:
0, 1, 2, 3, 4, 5, 6, 7, 8 and 9.
Once all numbers are placed into their respective buckets, we then work through each buckets in order starting from ‘Bucket 0’ and work our way to the last bucket, appending each number into a new list.
If the numbers being sorted have more than one digit (i.e. > 9) then we need to apply this process for each digit in the number. The same process of placing into buckets is applied using this new list.
Note - We need to account for the number of digits present in the largest number. Any smaller numbers need leading zeroes added to make the numbers have the same ‘size’.
If we were sorting a list containing the numbers 1024 and 512, we would need to format the second number as 0512.
Example of Radix Sort:
Suppose we have the following unsorted Array: 10, 02, 99, 54, 14
Using the Least Significant Digit (LSD) approach - working the digits right to left:
First Iteration = 10, 02, 99, 54, 14
Place each number in the ‘Bucket’ that corresponds with the value in the units column (in bold):
Bucket 0: 10
Bucket 1:
Bucket 2: 02
Bucket 3:
Bucket 4: 54, 14
Bucket 5:
Bucket 6:
Bucket 7:
Bucket 8:
Bucket 9: 99
Starting from Bucket 0, we concatenate the numbers in order to form
Array: 10, 02, 54, 14, 99
As there are two digits in each number, we repeat the process:
Second Iteration = 10, 02, 54, 14, 99
The next iteration moves a digit left to the tens column of each number being sorted:
Bucket 0: 02
Bucket 1: 10, 14
Bucket 2:
Bucket 3:
Bucket 4:
Bucket 5: 54
Bucket 6:
Bucket 7:
Bucket 8:
Bucket 9: 99
Again, start from Bucket 0 and build the list back up to form:
Array: 02, 10, 14, 54, 99
Sorted!
Variations of Radix Sort:
There are different approaches to the Radix Sort, depending which digit you start sorting from:
Most Significant Digit (MSD) - Left to Right
Least Significant Digit (LSD) - Right to Left (shown in example)
Least Significant Digit approach ensures that the algorithm is stable - elements with equal values appear in the sorted list in the same order as they were in the unsorted list.