Radix Sort

Algorithm

Assuming we have data comprised of numbers with digits limited to $k$. In this case, the data will be sorted according to the following algorithm, and its time complexity is $O (n)$.

Sort by comparing the $i = 1 , \cdots , k$th digits of each number.

Explanation

Radix Sort is a clever method that can sort data in linear time without comparing the data elements, overcoming the limits of comparison sorting algorithms since it’s limited to datasets without floating-point numbers due to digit limitation.

Example

$$ 190 \\ 812 \\ 9 \\ 77 \\ 21 \\ 413 $$ For instance, a dataset of $n=6$ numbers limited to digits of $k=3$ can be sorted in $3 \cdot 6 = 18$ passes. By first sorting by the $i=1$th digit, $$ 19 {\color{red}0} \\ 02 {\color{red}1} \\ 81 {\color{red}2} \\ 41 {\color{red}3} \\ 07 {\color{red}7} \\ 00 {\color{red}9} $$ then by the $i=2$th digit, $$ 0 {\color{red}0} 9 \\ 8 {\color{red}1} 2 \\ 4 {\color{red}1} 3 \\ 0 {\color{red}2} 1 \\ 0 {\color{red}7} 7 \\ 1 {\color{red}9} 0 $$ and finally by the $i=k$th digit, $$ \color{red}{0} 0 9 \\ {\color{red}0} 21 \\ {\color{red}0} 77 \\ {\color{red}1} 90 \\ {\color{red}4} 13 \\ {\color{red}8} 12 $$ it is important to note that since $k$ is given as a constant number of digits, the result is trivially $kn = O(n)$. However, if the digit count exceeds the number of data elements, the complexity becomes $O(n^2)$. In such cases, it is better to use a comparison sorting algorithm.

Proof

Strategy: If you’ve understood the process above, there’s literally no need to see a proof.

To sort numbers from $0$ to $9$, you simply gather and then merge numbers according to each digit. If it’s $0$, gather all $0$s together, if it’s $1$, gather all $1$s together, …, if it’s $9$, gather all $9$s together into an array and then merge them in order, thus completing the sort for that digit. Repeat this for digits up to $k$, resulting in a total operation count of $k n = O(n)$.

■

Code

Here’s an implementation of Radix Sort in Julia.