← Back to the sorting page
Non-Comparison Sorts (Counting, Radix, Bucket)
Beat the O(n log n) comparison lower bound by not comparing: count occurrences, sort digit by digit, or scatter into buckets.
What to know
- Counting sort needs a bounded integer range k; O(n + k) time and space.
- LSD radix sort applies a stable counting sort per digit — 32-bit ints in 4 byte-passes.
- Bucket sort assumes roughly uniform distribution; each bucket insertion-sorts.
In the wild: Suffix-array construction, GPU sorts, histogram binning, sorting network packets by port.
Algorithms to reach for
Counting sort
O(n + k)Small-range integers (ages, grades, bytes)
Radix sort (LSD)
O(d · (n + b))Fixed-width ints/strings without comparisons
Bucket sort
O(n) averageUniformly distributed floats
Practice problems — with full guides
Each problem has its own page: progressive hints, how to approach it, and the full solution.