Radix Sort - PCCST303

Every sort so far, selection, insertion, quick, merge, heap, works by comparing pairs of elements. Radix sort doesn't compare elements against each other at all: it sorts by looking at individual digits.

Idea

Definition

Radix sort sorts integers by processing one digit position at a time, from the least significant digit (LSD) to the most significant, using a stable counting-style pass at each position to group numbers by that digit's value.

Key Idea

The order matters: sorting least significant digit first works because each later pass is stable, so it never disturbs the relative order established by an earlier (less significant) pass among numbers that tie on the current digit. Sorting most-significant-digit-first would need a fundamentally different (recursive bucket) approach to get the same guarantee.

Algorithm

RADIX_SORT(A, N)
// A is the array to sort
// N is the number of elements in A
 
1. MAX = the largest value in A
2. D = 0
3. While 10^D <= MAX:
       COUNTING_SORT_BY_DIGIT(A, N, D)
       D = D + 1
4. Stop.

Each pass is itself a counting sort restricted to the digit range 0-9:

COUNTING_SORT_BY_DIGIT(A, N, DIGIT_POSITION)
// A is the array to sort
// N is the number of elements in A
// DIGIT_POSITION is which digit to sort by (0 = ones, 1 = tens, ...)
 
1. Create COUNT[0..9], all zero.
2. For i = 0 to N-1:
       D = digit of A[i] at DIGIT_POSITION
       COUNT[D] = COUNT[D] + 1
3. For D = 1 to 9:
       COUNT[D] = COUNT[D] + COUNT[D-1]      // running total = final positions
4. For i = N-1 down to 0:                     // backward, to stay stable
       D = digit of A[i] at DIGIT_POSITION
       OUTPUT[COUNT[D] - 1] = A[i]
       COUNT[D] = COUNT[D] - 1
5. Copy OUTPUT back into A.

Step 4 scans backward through the input specifically to keep the sort stable: placing later-indexed elements first would let an earlier element land in a later position, disturbing relative order among elements with the same digit.

Worked example

Sorting [170, 45, 75, 90, 802, 24, 2, 66]. Maximum is 802, three digit positions: ones, tens, hundreds.

Index

170

802

01234567

Pass 1: sort by ones digit

Number	Ones digit
170	0
45	5
75	5
90	0
802	2
24	4
2	2
66	6

Grouped by ones digit, preserving original left-to-right order within each group (that's the stability): digit 0 → 170, 90; digit 2 → 802, 2; digit 4 → 24; digit 5 → 45, 75; digit 6 → 66.

Index

170

802

01234567

Pass 2: sort by tens digit

Number	Tens digit
170	7
90	9
802	0
2	0
24	2
45	4
75	7
66	6

Grouped by tens digit, in the order they appear after pass 1: digit 0 → 802, 2; digit 2 → 24; digit 4 → 45; digit 6 → 66; digit 7 → 170, 75; digit 9 → 90.

Index

802

170

01234567

Pass 3: sort by hundreds digit

Number	Hundreds digit
802	8
2	0
24	0
45	0
66	0
170	1
75	0
90	0

Grouped by hundreds digit: digit 0 → 2, 24, 45, 66, 75, 90 (in that order, carried over from pass 2); digit 1 → 170; digit 8 → 802.

Index

170

802

01234567

Fully sorted after three passes, no comparisons between whole numbers were ever made.

Complexity

Measure	Complexity
Time	O(d(n + k)), where `d` is the number of digits, `n` is the number of elements, and `k` is the digit range (10 for base-10)
Space	O(n + k), extra output array plus count array

For fixed-width numbers (e.g. all values under some constant like 10⁵), d is a constant, making radix sort effectively O(n), faster than any comparison-based sort's O(n log n) lower bound. The trade-off: radix sort only works on data with a well-defined digit/character structure (integers, fixed-length strings), not arbitrary comparable objects.

Comparison sorts vs radix sort

Feature	Selection/Insertion/Quick/Merge/Heap	Radix sort
Basis	Compares pairs of elements	Groups by digit value, no comparisons
Lower bound	O(n log n)	O(d·n), can beat O(n log n) for fixed-width data
Works on	Any comparable type	Integers, fixed-length strings (structured data)
Stability requirement	Optional design choice	Required at every pass, or the result is wrong

Quick recall

Sorts digit by digit, from least significant to most significant, using a stable pass (typically counting sort) at each digit position.
Correctness depends entirely on every pass being stable; an unstable digit-pass would undo the ordering built by earlier, less-significant passes.
O(d(n+k)) time, effectively O(n) when digit count d is bounded, beating the O(n log n) lower bound that applies to comparison-based sorts.
Only applies to data with digit/character structure, not general comparable objects.