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.