Comparison Sorts and the $\Omega(n \log n)$ Lower Bound

A comparison sort decides the final order by comparing pairs of elements. Any such algorithm corresponds to a decision tree: each internal node is a comparison, each leaf is a final permutation. With $n!$ possible permutations, the tree has at least $n!$ leaves, so its height is at least $\log_2(n!) = \Theta(n \log n)$.

What this means

Any algorithm whose only access to elements is comparisons must take $\Omega(n \log n)$ comparisons in the worst case. Merge sort and heap sort hit this bound. Quicksort is $O(n \log n)$ on average but $O(n^2)$ worst case.

When can you go faster?

If elements have additional structure — small integer keys, fixed-length strings, floats in a known range — you can use non-comparison sorts (counting sort, radix sort, bucket sort) and achieve linear time. The lower bound applies only to comparison-based methods.

In-place and stable

In-place sorts use $O(1)$ or $O(\log n)$ auxiliary space. Stable sorts preserve the relative order of equal elements — important when you sort by one key and want previous sort order preserved as a tiebreaker.

| Algorithm | Time (avg) | Time (worst) | Space | In-place | Stable | |-----------|-----------|--------------|-------|----------|--------| | Merge sort | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ | No | Yes | | Quicksort | $O(n \log n)$ | $O(n^2)$ | $O(\log n)$ | Yes | No | | Heap sort | $O(n \log n)$ | $O(n \log n)$ | $O(1)$ | Yes | No | | Insertion sort | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Yes | Yes |

In practice

Production sort routines are typically hybrid — Timsort (Python's `sorted`, Java's Arrays.sort for objects) is a merge sort variant tuned for nearly-sorted real-world data. Introsort (C++ std::sort) starts with quicksort and falls back to heap sort if recursion depth gets too deep.