The Magic of Radix Sort

Radix Sort is a sorting algorithm which does not rely on comparison and achieves highly optimized time complexity of O(n). Although it is not suitable for numbers containing too many digits, we developers can leverage its speed to solve specific problems.

The genius design of Radix Sort is that it exploits the fact that a single digit has only 10 possible values (zero to nine). First, it initializes ten "buckets." Each one is designed for storing the numbers that have the corresponding digit. Second, Radix Sort uses the buckets to sort the input, which is putting the numbers in the bucket with their digits. This process has to consider the digit from the least significant digit (LSD) to the most significant digit (MSD) in order to guarantee the sorting stability and the complexity. Then the algorithm repeats the process until the sorting of the most significant digit is done. While at every cycle Radix Sort writes back the numbers to the original array, at the next time that it scans the array from the beginning, it preserves the results of the previous cycle. With this operation, the numbers which have the same lower digits won't change order unless some of them have bigger high digits and get placed to larger bucket in the remaining cycles. In addition, if we want the "bucket" to work well, we usually make it a queue so that we can push and pop elements in a FIFO (First-In, First-Out) order to maintain stability. Otherwise, we could use a standard vector and perform the write-back in reverse order.

Insight: I'm impressed by the optimized O(n) complexity of Radix Sort. It turns out that if we abandon the comparison model, the optimization of sorting algorithm can go further. For memorizing, I think it is better to emphasize the concept of "bucket" and "non-comparison-based sorting."