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.