Sorting algorithms arrange elements in order. Comparison sorts have an O(n log n) lower bound proven by decision tree argument. Non-comparison sorts can achieve O(n) by exploiting key structure.
Sorting is the task of arranging a list in order — and choosing the right algorithm determines whether the task takes milliseconds or hours.
Why sorting matters
Sorting is one of the most studied problems in computer science. A sorted list enables binary search (O(log n) vs. O(n)). Sorting is a prerequisite for many other algorithms. And sorting benchmarks reveal fundamental limits: the best possible comparison-based sort is Θ(n log n) — provably. No comparison sort can do better.
| Algorithm | Best | Average | Worst | Space | Stable? |
|---|---|---|---|---|---|
| Merge Sort | Θ(n log n) | Θ(n log n) | Θ(n log n) | O(n) | Yes |
| Quicksort | Θ(n log n) | Θ(n log n) | Θ(n²) | O(log n) | No* |
| Heapsort | Θ(n log n) | Θ(n log n) | Θ(n log n) | O(1) | No |
| Insertion Sort | Θ(n) | Θ(n²) | Θ(n²) | O(1) | Yes |
| Bubble Sort | Θ(n) | Θ(n²) | Θ(n²) | O(1) | Yes |
| Counting Sort | Θ(n+k) | Θ(n+k) | Θ(n+k) | O(n+k) | Yes |
* Stable quicksort implementations exist but the standard in-place version is not stable. k = range of values for counting sort.
Stability
A sort is stable if equal elements remain in their original relative order. Sorting records by last name: if two records have the same last name, a stable sort preserves their original order. Merge sort is always stable. Python's built-in sort (sorted() / list.sort()) uses Timsort — stable. Java's Arrays.sort() for objects uses merge sort — stable. Java's Arrays.sort() for primitives uses dual-pivot quicksort — not stable.
The O(n log n) lower bound for comparison sorts
Any algorithm that sorts by comparing elements must make at least Ω(n log n) comparisons in the worst case. Proof by decision tree: a sort algorithm that works by comparisons can be modelled as a binary decision tree where each internal node is a comparison and each leaf is a permutation. There are n! possible orderings — so the tree has at least n! leaves. A binary tree of depth d has at most 2d leaves. Therefore depth ≥ log₂(n!) = Θ(n log n) by Stirling's approximation. Any comparison-based sort must have worst case Ω(n log n). This bound is proven in CLRS §8.1.
Non-comparison sorts
Counting sort, radix sort, and bucket sort are not comparison sorts — they exploit structure in the key values themselves. Counting sort runs in O(n+k) time where k is the range of values. If k = O(n), this is O(n) — beating the comparison sort lower bound. The lower bound applies only to comparison-based algorithms; these algorithms don't compare elements, so the bound doesn't apply.
Python's Timsort
Python's built-in sort uses Timsort (Tim Peters, 2002). Timsort is a hybrid algorithm: it detects natural runs (already-sorted subsequences) in the data, extends short runs using insertion sort (which is fast for small n due to low constant), then merges runs using a merge sort strategy. Worst case: Θ(n log n). Best case: Θ(n) on already-sorted data. Stable. Space: O(n). Specified in the Python documentation and CPython source (Objects/listobject.c).
The comparison sort lower bound: formal proof
Formally (CLRS 4th ed., §8.1): model any comparison sort as a decision tree T. Each internal node corresponds to a comparison a𝑖 ≤ a𝑗. Each leaf corresponds to one of the n! possible permutations. Since every leaf must be reachable (any permutation is a valid input), T must have at least n! leaves. A binary tree of height h has at most 2h leaves, so h ≥ log₂(n!). By Stirling's approximation: log₂(n!) = Θ(n log n). Therefore any comparison sort requires Ω(n log n) comparisons in the worst case.
Integer sorting and the RAM model
The Ω(n log n) lower bound assumes the RAM model with unbounded word size. If keys are w-bit integers and n ≤ 2w (realistic constraint), radix sort runs in O(wn) = O(n log n) time but with a much smaller constant than merge sort in practice. On a word-RAM model where w = Θ(log n), radix sort matches the comparison sort lower bound — but beats it in practice because the constant is smaller.
Cormen, T. H. et al. (2022). CLRS (4th ed.), §8.1 — Lower bounds for sorting. Peters, T. (2002). Timsort algorithm description — CPython source Objects/listobject.c. Python documentation: docs.python.org/3/library/functions.html#sorted.