Problem Statement

Radix Sort

Radix Sort puts numbers in order without ever comparing two numbers directly. Instead, it sorts them one digit at a time. Picture sorting a stack of mail by zip code. First you make piles by the last digit, gather them back up, then make piles by the next digit, and so on. Radix Sort does the same thing: it starts at the least significant digit (LSD), the ones place, and works its way left toward the most significant digit (MSD), the biggest place value. At each digit it uses a stable helper sort, meaning a sort that keeps equal items in the same order they came in. We use Counting Sort as that helper. The cost is O(d times (n + k)), where d is how many digits the biggest number has, n is how many numbers there are, and k is the base, which is 10 for normal decimal numbers. Radix Sort shines when you have a big pile of fixed-length integers or strings.

mediumSortingSorting AlgorithmsTime: 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.

Trace it on `arr=[170, 45, 75, 90, 802, 24, 2, 66]`

init: max_val=802, exp=1 (since 802//1 > 0, enter loop)
exp=1 (ones digit): keys 0,5,5,0,2,4,2,6 -> stable counting sort -> arr=[170, 90, 802, 2, 24, 45, 75, 66]
exp*=10 -> exp=10; 802//10=80 > 0, continue
exp=10 (tens digit): keys 7,9,0,0,2,4,7,6 -> stable sort (170 stays before 75) -> arr=[802, 2, 24, 45, 66, 170, 75, 90]
exp*=10 -> exp=100; 802//100=8 > 0, continue
exp=100 (hundreds digit): keys 8,0,0,0,0,1,0,0 -> stable sort -> arr=[2, 24, 45, 66, 75, 90, 170, 802]
exp*=10 -> exp=1000; 802//1000=0, loop ends
return [2, 24, 45, 66, 75, 90, 170, 802]

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.

Shape of the loop

maxVal = max(arr); exp = 1
while maxVal // exp > 0:        # one pass per digit position
    countingSortByDigit(arr, exp)   # STABLE sort on (num // exp) % 10
    exp *= 10                  # move LSD -> MSD
return arr

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Using an unstable sort per digit — that breaks the LSD-first invariant. Counting sort is the standard stable subroutine.

Sorting Algorithms Pattern