Why So Many Sorts? Comparison vs Non-Comparison and the Ω(n log n) Lower Bound
Sorting Algorithms Overview
A bird's-eye view of the sorting landscape — why no single algorithm wins every scenario, the theoretical floor for comparison-based sorts, and a cheat-sheet table comparing all major algorithms.
What you'll learn
- Explain why multiple sorting algorithms exist and when each shines
- State the Ω(n log n) lower bound for comparison sorts and why it holds
- Compare the key properties (time, space, stability) of common sorts
Every language standard library ships a sorting function, yet computer science textbooks devote entire chapters to a dozen different algorithms. Why? Because no single sort wins every trade-off. Input size, data distribution, memory budget, stability requirements, and even cache behaviour all push the optimal choice in different directions.
Two Families: Comparison vs Non-Comparison
Comparison sorts determine order solely by asking “is A less than B?” They work on any data type that supports a comparator. The cost is a hard theoretical floor: no comparison sort can do better than Ω(n log n) comparisons on average.
Non-comparison sorts (counting sort, radix sort, bucket sort) exploit the structure of the keys — typically that they are bounded integers. They sidestep the lower bound entirely, achieving O(n + k) time, but only when that structural assumption holds.
The Ω(n log n) Lower Bound
For comparison sorts the proof is elegant. Imagine a decision tree where every internal node is a comparison (A ≤ B?) and every leaf is one permutation of the input. For n elements there are n! possible permutations, so the tree must have at least n! leaves. A binary tree with L leaves has height at least log₂(L), giving a minimum height of log₂(n!) ≈ n log n (by Stirling’s approximation). The height of the tree equals the worst-case number of comparisons — hence Ω(n log n) is unavoidable.
The practical takeaway: merge sort, heap sort, and quicksort (average case) are all asymptotically optimal comparison sorts. Differences between them come from constants, cache behaviour, stability, and in-place vs extra-space trade-offs.
When to Reach for Each Sort
Small arrays (n < 20) — insertion sort wins because its low constant beats the
overhead of divide-and-conquer. Near-sorted data — insertion sort again (O(n)
best case). General purpose in the browser or Node — TimSort (what V8 uses).
Guaranteed O(n log n) with no extra space — heap sort. Stable and predictable —
merge sort. Bounded integers — counting or radix sort.
Algorithm Comparison Table
| Algorithm | Best | Average | Worst | Space | Stable | In-Place |
|---|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No | Yes |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Yes |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Yes |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(k) | Yes | No |
| Radix Sort | O(d·(n+b)) | O(d·(n+b)) | O(d·(n+b)) | O(n+b) | Yes | No |
| TimSort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
k = range of values; d = number of digits; b = base used in radix sort.
Up Next
Start with the simplest algorithm — it builds intuition for swapping and loop invariants before the more powerful sorts.
Bubble Sort →