Counting Sort & Radix Sort

Every sort you have seen so far, bubble, insertion, selection, merge, quicksort, decides order purely by comparing pairs of elements with `<` or `>`. It turns out no comparison-based sort can beat O(n log n) in the worst case: with n elements there are n! possible orderings, and each comparison only rules out at most half of the remaining possibilities, so you need at least log₂(n!) ≈ n log n comparisons to pin down the correct one. That bound sounds like a hard ceiling, but it only applies to algorithms that decide order by comparison. If you know something extra about your data, you can sidestep the bound entirely.

If your array holds non-negative integers within a known, small range (say, 0 to 100), you do not need to compare elements at all. You can just count how many times each value appears, then reconstruct the sorted array from those counts. This runs in O(n + k) time, where k is the range of values, no comparisons required.

Counting sort falls apart once the value range k gets huge relative to n. Counting sort on numbers up to a billion would need a billion-slot counts array. Radix sort fixes this by never counting the whole value at once. Instead, it sorts the numbers digit by digit, from the least significant digit to the most significant, using a stable counting sort as the subroutine for each digit position. After processing every digit, the array ends up fully sorted. Stability at each pass is what makes this work, since it preserves the ordering established by less-significant digits already processed.

• -Counting sort: O(n + k) time and O(k) extra space, best when the value range k is small relative to n.
• -Radix sort: O(d · (n + b)) time where d is the number of digits and b is the base (10 for decimal digits), best when values have a bounded, fixed-width representation.
• -Both only work on this kind of structured data (small-range or fixed-width non-negative integers). Neither can sort arbitrary comparable objects the way merge sort or quicksort can.