Radix Sort
mediumTime: O(d * (n + k))Space: O(n + k)
Signals to notice
sort by digit positionnon-comparison sortstable per-digit sorting
Brute force first
Comparison sort — O(n log n). Ignores fixed-width integer structure.
The key insight
Sort by LSD first using counting sort (stable), then next digit, etc. After d passes, fully sorted. O(d × (n + k)) where k = base, d = max digits.
What must stay true
Sorting from LSD to MSD with a STABLE sort preserves earlier digit orderings. After processing all digits, the array respects all digit positions simultaneously.
Easy way to go wrong
Using an unstable sort per digit — that breaks the LSD-first invariant. Counting sort is the standard stable subroutine.