Radix Sort — Breaking the O(n log n) Barrier

How Radix Sort Works

Radix Sort is a non-comparison-based sorting algorithm. Instead of comparing elements to each other, it sorts by processing individual digits (or characters) of the keys, from least significant to most significant (LSD) or vice versa (MSD).

LSD Radix Sort (Least Significant Digit First)

function radixSort(arr):
  maxVal = max(arr)
  for exp = 1 while maxVal / exp > 0, exp *= 10:
    countingSort(arr, exp)

Each pass uses Counting Sort as a stable subroutine to sort by one digit position. Stability is critical — it ensures that the ordering from previous passes is preserved.

Digit-by-Digit Example

Sorting [170, 45, 75, 90, 802, 24, 2, 66]:

Pass	Digit	Result
1	Ones	[170, 90, 802, 2, 24, 45, 75, 66]
2	Tens	[802, 2, 24, 45, 66, 170, 75, 90]
3	Hundreds	[2, 24, 45, 66, 75, 90, 170, 802]

Complexity

Metric	Value
Time	O(n * k) where k = number of digits
Space	O(n + b) where b = base (typically 10 or 256)
Stable	Yes
In-place	No

When Radix Sort Beats Comparison Sorts

The theoretical lower bound for comparison-based sorting is O(n log n). Radix Sort sidesteps this by not comparing elements. It is faster when:

• k (number of digits) is small relative to log n
• For 32-bit integers, k = 32/log₂(base). Using base 256: k = 4
• For n > 2⁴ = 16, Radix Sort with base 256 does fewer operations

MSD vs LSD

• LSD (Least Significant Digit first): Processes from rightmost digit. Simpler to implement, naturally stable.
• MSD (Most Significant Digit first): Processes from leftmost digit. Can short-circuit when keys have common prefixes. Used for string sorting.