Lower bounds and linear-time sorting
No comparison-based sort can beat O(n log n) in the worst case. But when keys have special structure, such as small integers, we can sort in linear time without comparing items at all.
The comparison model
Comparison sorts learn about the order only by asking 'is a less than b?' Merge sort, quicksort, heapsort, and insertion sort are all comparison sorts. The question is how few comparisons any such algorithm can need in the worst case.
The decision-tree argument
Model any comparison sort on n items as a binary decision tree: each internal node is a comparison, and each leaf is a final ordering. The tree must have at least n! leaves, one for every possible permutation of the input. A binary tree with n! leaves has height at least log2(n!), which is about n log2(n) - 1.44n, so some input needs that many comparisons: Omega(n log n).
What the bound means
Merge sort and heapsort are therefore asymptotically optimal comparison sorts. To sort faster, an algorithm must use more information about the keys than pairwise comparisons, for example that they are integers in a limited range, or digits of fixed length.
Counting sort
If keys are integers from 0 to k, counting sort counts how many times each value occurs, computes running totals to find where each value's block begins, then places each item in its position. It runs in O(n + k) time and O(n + k) space, and placing items from right to left keeps it stable. It is excellent when k is not much larger than n.
Radix sort
Radix sort sorts by digits. Least-significant-digit radix sort applies a stable sort, usually counting sort, to the last digit, then the next, up to the most significant. Stability ensures earlier digit orderings are preserved. For n numbers of d digits in base b, it takes O(d(n + b)), linear when d is constant, as for 32-bit integers sorted by bytes.
Bucket sort
Bucket sort divides the key range into n equal buckets, places each item in its bucket, sorts each bucket, usually with insertion sort, and concatenates them. If keys are spread uniformly, such as random numbers in [0, 1), each bucket holds about one item and the expected time is O(n). Badly skewed data can put everything in one bucket.
Selection and partial sorting
Often you need only part of the order. Quickselect finds the kth smallest item in expected O(n) time by partitioning and recursing into only the side that contains position k; the median-of-medians algorithm guarantees O(n) worst case. Finding the top k items with a heap costs O(n log k). Both avoid the full O(n log n) sort.
Worked example
Counting sort on [3, 1, 4, 1, 0, 3] with keys 0 to 4. Counts for 0 to 4: [1, 2, 0, 2, 1]. Running totals of earlier counts give starting positions [0, 1, 3, 3, 5]. Placing items yields [0, 1, 1, 3, 3, 4]. For comparison, log2(6!) = log2(720) is about 9.5, so any comparison sort needs at least 10 comparisons in the worst case for 6 items, while counting sort made none.
Key takeaways
Comparison sorts learn order only through comparisons. A decision tree for n items needs at least n! leaves, so height at least log2(n!), about n log2 n: no comparison sort beats Omega(n log n) in the worst case, making merge sort and heapsort optimal. Counting sort sorts integers in 0 to k in O(n + k), stably. LSD radix sort applies stable digit sorts in O(d(n + b)). Bucket sort averages O(n) on uniform data. Quickselect finds the kth smallest in expected O(n); median-of-medians guarantees it.
Flashcard
Learns order only by comparing pairs
Check your understanding
How can counting sort beat the Omega(n log n) lower bound?