Radix Sort
Prerequisites
Before reading this article, you should first learn:
Summary in One Sentence
Radix Sort is an extension of the Counting Sort algorithm. Its main idea is to perform counting sort on each digit of the elements sequentially. Since counting sort is stable, after completing the counting sort for each digit, all elements are sorted.
The visualization panel below demonstrates the process of radix sort: click the line let maxLen = 0 to see how the algorithm converts array elements into non-negative numbers; click the line countSort(nums, k) multiple times to perform counting sort on each digit; finally, click the line nums[i] -= offset to convert the array elements back to their original values, completing the sort:
First, let us clarify the term Radix Sort.
The term "Radix" refers to the base of a number system. For example, the radix of the decimal system is 10, while for the binary system, it is 2. From the name, we can infer that this sorting algorithm is related to numerical bases, which means it is not a general-purpose sorting algorithm. The data to be sorted must be integers or convertible to integers through some rule to use radix sort.
I have noticed that many online sources group radix sort with bucket sort, considering radix sort as an application of bucket sort.
However, I disagree with this view. I believe radix sort is an extension of counting sort, used to address the high space complexity of counting sort, and has little to do with bucket sort.
Now that you have already learned Counting Sort and Bucket Sort, you can reflect on whether radix sort is an extension of counting sort or bucket sort after I explain its principles.
Principles of Radix Sort
The principle of radix sort is quite simple. For example, if the input array consists of three-digit numbers, nums = [329, 457, 839, 439, 720, 355, 350], we first sort by the units digit, then by the tens digit, and finally by the hundreds digit. This completes the sorting of the entire array.
The key here is that the sorting of each digit must be stable; otherwise, the final result will be incorrect.
Let's use the nums array as an example to demonstrate the process of radix sort. I will write each number vertically to make it easier to see the effect of sorting each digit.
First, the initial state:
329
457
839
439
720
355
350Performing a stable sort based on the unit digit results in:
720
350
355
457
329
839
439
^Next, perform a stable sort based on the tens digit to obtain:
720
329
839
439
350
355
457
^Finally, perform a stable sort based on the hundreds place to obtain:
329
350
355
439
457
720
839
^The above is the process of radix sort. Before providing the solution code, let's address some questions about radix sort:
Why must a stable sort be used for each digit?
What stable sorting method is preferable, and why?
What if the numbers in the array to be sorted are not all three-digit numbers? What if there are negative numbers?
Must sorting be done from the least significant digit to the most significant digit? Can it be reversed, sorting from the most significant digit to the least significant digit?
Why a Stable Sort is Necessary for Each Digit
Here's a simple example:
56
57The units place is already sorted, and now we need to sort by the tens place.
The tens digit is 5 for both numbers. A stable sort ensures that the order of these two 5s remains unchanged, resulting in a correct final order. However, if an unstable sort is used, the order of these 5s might get disrupted, leading to an incorrect result.