Radix Sort
mediumTime: O(d * (n + k))Space: O(n + k)
Recognize the pattern
sort by digit positionnon-comparison sortstable per-digit sorting
Brute force idea
Comparison sort — O(n log n). Ignores fixed-width integer structure.
Better approach
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.
Key invariant
Sorting from LSD to MSD with a STABLE sort preserves earlier digit orderings. After processing all digits, the array respects all digit positions simultaneously.
Watch out for
Using an unstable sort per digit — that breaks the LSD-first invariant. Counting sort is the standard stable subroutine.