Counting Sort and Radix Sort

Comparison-based sorts like quicksort or mergesort can't beat $O(n \log n)$ in the worst case — that limit is provable, because any algorithm that only compares pairs of elements needs at least that many comparisons to distinguish all possible orderings. Counting sort sidesteps the limit entirely by never comparing elements at all: if you know every value in an array of $n$ integers falls between $0$ and $k$, you can count how many times each value $0, 1, \dots, k$ appears, then read off the sorted array directly from those counts, in $O(n + k)$ time.

Radix sort extends the same idea to numbers too large to count directly (say, 32-bit integers, where $k$ would be billions). It sorts digit by digit — first by the ones digit, then the tens digit, then the hundreds, and so on — using counting sort as a stable subroutine at each digit position. After processing every digit, the whole array ends up fully sorted, in $O(d(n+k))$ time where $d$ is the number of digits and $k$ is the number of possible digit values (10, for base-10 digits).

For example, sorting the array [170, 45, 75, 90] by ones digit first gives [170, 90, 45, 75], then by tens digit gives [170, 90, 45, 75] → [90, 170, 45, 75]... continuing through all digit positions leaves the fully sorted [45, 75, 90, 170] — no two elements were ever directly compared.