Radix Sort
Radix Sort Animation
Radix Sort Infographic
Methodology
From a high level, Radix Sort works by sorting integers from the least significant digit to the most significant digit. Below are the specific steps.
Determine the maximum number of digits
Select digits at current place index
Do Counting Sort based on selected digits
Increment current place index
Repeat (1) through (3)
stop once current place index equals maximum number of digits
Note, the reason why Counting Sort is recommended as the intermediate sorting algorithm in step(3) is because it’s fast over a small range of numbers. Keep in mind it is the base of numbers being sorted which determines the range. For example, when numbers being sorted are in base 10, that means each digit can take on only 10 possible values (0-9). Similarly, when numbers being sorted are given in base 2, each digit can be only 2 possible values (0, 1).
Caveat
Radix Sort works well with positive integers. It can work for Floats and negative numbers too but the data needs to be preprocessed.
Complexity
Given
B = digits in base
P = max number of digit places
Time Complexity: P * (N + B)
Space Complexity: N + B
Stable
