Sorts that beat O(n log n) by not comparing keys: counting, radix and bucket sort.
Bucket sort distributes elements into buckets by value, sorts each bucket, then concatenates. It runs in O(n+k) average time when elements are roughly…
Counting sort is a non-comparison sort for integers in a small range [0, k). It tallies how often each value appears, computes a prefix sum to get final…
Radix sort is a non-comparison sort that processes integer keys digit by digit, using a stable bucket sort at each digit. It runs in O(n·k) time where k is…
Any algorithm that sorts only by comparing pairs of keys needs Ω(n log n) comparisons in the worst case, because there are n! possible orderings and each comparison can at best halve the remaining possibilities. Non-comparison sorts sidestep that bound by inspecting the keys themselves: using a key as an array index, splitting it into digits, or mapping it to a value range. The price is an assumption about the keys, such as "small non-negative integers" or "uniformly distributed in [0, 1)". When the assumption holds, these sorts run in linear time; when it fails, they waste memory or degrade badly.
Counting sort is the primitive: it tallies occurrences of each integer key and computes final positions from a prefix sum. Radix sort applies a stable counting sort once per digit (least significant digit first), which keeps the counter array small even for 32- or 64-bit keys. Bucket sort takes a different route: it scatters values into buckets that cover equal slices of the key range, sorts each small bucket with an ordinary sort such as insertion sort, and concatenates. All three trade generality for speed.
| Algorithm | Keys | Time | Extra space | Stable | Use when |
|---|---|---|---|---|---|
| Counting Sort | Integers in [min, max] | O(n + k) | O(n + k) | Yes | Range k is about n or smaller |
| Radix Sort | Fixed-width integers or strings | O(d · (n + b)) | O(n + b) | Yes (LSD) | Many keys with a wide range, few digits d in base b |
| Bucket Sort | Reals, roughly uniform | O(n) average, O(n²) worst | O(n + buckets) | If inner sort is | Data is evenly spread over a known range |
In practice, general-purpose libraries use comparison sorts (Python's Timsort, introsort, pdqsort) because they make no assumptions. Non-comparison sorts appear inside specialised code: GPU sorting (radix sort is the standard GPU sort), database engines sorting fixed-width keys, histogram-based processing, and suffix-array construction. They are also a staple interview topic because they show why the n log n bound is a statement about a model of computation, not about sorting as such.
For the comparison-based sorts and an overall map of sorting algorithms, return to Algorithms.