Sorting by digits
Radix sort orders fixed width keys by processing them one digit at a time, never comparing whole keys. Each pass sorts on a single digit position using a stable sub sort, usually counting sort.
Least significant first
- The common variant starts at the least significant digit and moves toward the most significant.
- Each pass must be stable so that the order established by earlier, less significant digits survives.
- After the final pass on the most significant digit, the whole array is sorted.
Why stability is essential
- When two keys share the current digit, the stable pass keeps their existing relative order.
- That existing order encodes all the lower digit comparisons already done, so it must not be disturbed.
- Lose stability and the partial order from previous passes is corrupted.
Cost and limits
- Total work is the number of digits times the cost of one stable pass, which is roughly the item count plus the digit alphabet size.
- It shines when keys are short and there are many of them, beating comparison sorts on bulk integers or fixed length strings.
- It needs a meaningful notion of digits and extra space for the stable pass.
Key idea
Radix sort sorts keys one digit at a time with a stable pass per position, turning many short keys into a sort that needs no whole key comparisons.