Radix sort (LSD)
Radix sort (least-significant-digit first) sorts numbers by repeatedly running a stable counting sort on one digit at a time, starting from the ones place and working up through the tens, hundreds, and so on. After every digit place has been processed, the array is fully sorted.
When it is the right choice
Radix sort is worth using for sorting large collections of fixed-width integers, where its O(d(n + b)) time — d digit passes over n values, each pass a base-b counting sort — beats a comparison sort's O(n log n) once n is large enough relative to the digit count d. It is a poor fit for values with many digits or an unbounded range, since every extra digit is another full pass over the whole array.
How it works
- Starting from the last digit (the ones place), repeat the following for each digit place in turn.
- Count how many values have each digit, zero through nine, in the current place.
- Turn those counts into positions by adding each count to the running total of all smaller digits.
- Working from the last value to the first, place each value at its position for this digit and reduce that count by one.
- Once every digit place has been processed, the array is fully sorted.
Worth noticing
- Its comparisons counter stays at zero for the entire run, exactly like counting sort — each digit pass counts and places values, and never asks whether one value is greater than another.
- It must process digits from least significant to most significant, and each digit's pass must be stable, or an earlier digit's ordering gets destroyed by a later one.
- The counts track is always exactly ten cells, one per digit, no matter how large the values are — the number of passes grows with the number of digits, not the width of any one pass.
Cost
- Best
- O(d(n + b))
- Average
- O(d(n + b))
- Worst
- O(d(n + b))
- Extra space
- O(n + b)
- Stable
- Yes