How radix sort works
- Find the largest value. Its number of digits is the number of passes.
- The first pass looks only at the ones digit. Count how many values have each digit from 0 to 9.
- Turn the counts into running totals. Each total says where the last value with that digit goes in the output.
- Walk through the array from right to left. Put each value at the position its digit's total points to, lower that total by one, and at the end copy the output back.
- Repeat for the tens digit, then the hundreds digit, until the largest value has no digits left.
What the colours mean
In each pass the digit being read is underlined in red in the labels under the bars. occurrences holds the ten digit counters, and outputArr fills up as values are placed. Yellow is read and pink is written.
Radix Sort time and space complexity
| Best case | Average case | Worst case | Extra space | Stable |
|---|---|---|---|---|
| O(d × n) | O(d × n) | O(d × n) | O(n) | Yes |
d is the number of digits in the largest value. Each pass walks through the array a fixed number of times and uses 10 counters, so the total is d passes over n values. A largest value of 999 means 3 passes, whether the array holds 5 values or 30.
Radix sort depends on every pass being stable. Walking from the right while the totals count down keeps values with the same digit in the order the previous pass left them, so the order by ones digit survives the pass over the tens.
The C# code
The listing beside the bars is the GetMaxVal(), RadixSort() and CountingSort() methods from Radix Sort in C#. The article explains the code and measures it with BenchmarkDotNet.
FAQ
Is radix sort stable?
Yes, and it has to be. Every pass keeps values with the same digit in their earlier order. Without that, the work of the previous passes would be lost.
Does radix sort work with negative numbers?
RadixSort() here expects values from 0 up. The article adds RadixSortWithNegatives(), which subtracts the smallest value from every element, sorts, and adds it back.
Why does radix sort start with the last digit?
Sorting by the least important digit first lets each later pass override it while keeping ties in order. After the pass over the most important digit, the whole numbers are in order.