Radix Sort is a non-comparative sorting algorithm. Unlike traditional sorting methods that compare elements directly like Merge Sort, Radix Sort processes individual digits of numbers, which allows it to efficiently sort lists of integers (and even strings of characters, with the right adjustments).
How Does Radix Sort Work?
At its core, Radix Sort organizes numbers by processing their individual digits. It operates on the principle that, given a set of integers, one can sort them first by the least significant digit (LSD), then the next least, and so on until the most significant digit (MSD). Radix Sort often employs Counting Sort as its subroutine for sorting the digits on each step.
The steps of Radix Sort
The process can be broken down into two main steps, iterated over each digit:
- Sorting by Each Digit: For each digit (starting with the LSD and moving to the MSD), Radix Sort applies Counting Sort to sort the numbers based on that digit’s value as the key for sorting. Since Counting Sort is efficient for small, finite ranges (in this case, 10 possible values for each digit in base-10 numbers), it’s perfectly suited for this task.
This process ensures that at each step, the numbers are sorted according to the current digit, while previous digits’ sorted order is maintained. - Iterative Sorting: After sorting by the least significant digit, Radix Sort iteratively applies Counting Sort for the next significant digit, progressively building up to a fully sorted array. With each iteration, the sorted order of the previous digits is preserved, leading to a completely sorted array once the most significant digit has been processed.
We added leading zeros at the beginning of each number so they have the same number of digits.
The Importance of Stable Sorting
Stable sorting is crucial for Radix Sort’s accuracy, ensuring that the relative order of items with the same digit is preserved across passes.
What is Stable Sorting?
In a stable sorting, elements that compare as equal retain their original relative order after the sorting process is completed.
Let’s assume we are trying to sort the following list:
After stable sorting:
Notice that the blue 1-digit came before the purple 1-digit and the red 3-digit came before the green 3-digit, maintaining their original relative order.
What would happen if we didn’t use a stable sort?
Using a non-stable sort as the subroutine for Radix Sort would undermine the algorithm’s core mechanism, leading to incorrect sorting results. A non-stable sort, by definition, does not guarantee that equal elements will retain their original order, which can disrupt the intended ordering as the sorting progresses through each digit or character.
Consider sorting the following list of numbers based on their individual digits, from least significant to most significant in ascending order: [95, 93].
First, we sort the list by the LSD. Both numbers have distinct LSDs (5 and 3), so this step correctly arranges them as [93, 95] regardless of the sorting algorithm’s stability, because we’re sorting by unique values.
Next, we sort by the MSD. a stable sorting algorithm would maintain their current order, resulting in the correct final order of [93, 95]. However, if a non-stable sorting algorithm is used for this step, it does not guarantee that the order of [93, 95] will be preserved. Because the algorithm is non-stable, it could incorrectly reorder the numbers. This can give us a final result of [95, 93], which was our original unsorted list.
Radix Sort Analysis
Runtime Complexity
The runtime complexity of Radix Sort can be broken down as follows:
- Number of Passes (k): Radix Sort processes each digit of the numbers, requiring k passes over the data, where k is the number of digits in the longest number in the dataset. For example, if the largest number is 9999, k=4 because there are four digits to process.
- Counting Sort Complexity (O(n + b)): For each pass, Radix Sort uses Counting Sort, which has a runtime complexity of O(n+b), where n is the number of elements to sort, and b is the base of the numbers (e.g., b=10 for decimal numbers).
Combining the above, the overall runtime complexity of Radix Sort when using Counting Sort as its subroutine is O(k⋅(n+b)). This reflects the k passes applying Counting Sort on each pass.
Space Complexity
The space complexity of Radix Sort, when using Counting Sort as a subroutine, combines the space needed for the Radix Sort process itself and the space required by Counting Sort for its operations.
- Counting Sort Space Requirement: Counting Sort has a space complexity of O(n+k), where n is the number of elements to sort, and k is the range of input values. In the context of Radix Sort, this k effectively becomes b, representing the base of the numbering system (e.g., b=10 for decimal numbers), making the space complexity of Counting Sort O(n+b).
- Radix Sort Space Requirement: Radix Sort needs a temporary array to store the sorted output for each digit-processing pass. The size of this temporary array is proportional to the input array, i.e., O(n), where n is the number of elements in the input array.
Combining the above, the overall runtime complexity of Radix Sort when using Counting Sort as its subroutine is O(n+b).
Conclusion
Radix Sort stands out in the realm of sorting algorithms for its distinctive approach and efficiency under the right conditions. While it may not be the universal choice for every sorting task, it can be efficient in specific contexts—particularly those involving large sets of numbers with a relatively small range of digits.