The Comparison-Based Sorting Lower Bound

Statement

Any comparison-based sorting algorithm must perform $\Omega(n \log n)$ comparisons in the worst case to sort $n$ elements.

A comparison-based sort uses only pairwise comparisons ($\le$ or $>$) to determine the relative order of elements. It makes no assumptions about the values (no counting, no hashing, no radix).

Proof via Decision Trees

A decision tree models the behaviour of any comparison-based sort:

• Each internal node represents a comparison $A[i] \le A[j]$, with two outgoing edges (Yes/No).
• Each leaf represents a specific permutation of the input — the sorted output.
• A path from root to leaf corresponds to the sequence of comparisons made on some input.

For $n$ distinct elements, there are $n!$ possible input permutations. Since the algorithm must be correct for all permutations, the decision tree must have at least $n!$ leaves.

A binary tree of height $h$ has at most $2^h$ leaves. Therefore:

$2^h \ge n!$

Taking logarithms:

$h \ge \log_2(n!)$

Using Stirling’s approximation ($n! \approx \sqrt{2\pi n}(n/e)^n$):

$\log_2(n!) = n \log_2 n - n \log_2 e + O(\log n) = \Omega(n \log n)$

The height $h$ is the number of comparisons on the longest path, so the worst-case number of comparisons is $\Omega(n \log n)$. $\square$

Implications

• MergeSort at $\Theta(n \log n)$ is asymptotically optimal amongst comparison sorts.
• HeapSort at $O(n \log n)$ is also optimal.
• QuickSort averages $\Theta(n \log n)$ but can degrade to $\Theta(n^2)$.
• No comparison sort can beat $\Omega(n \log n)$ in the worst case.

Lower Bound on Swaps

A separate result: the worst-case number of swaps is $\Omega(n)$. Consider the input $[2, 3, \ldots, n, 1]$. Every item is out of position, and each swap moves at most two items to their correct positions. Therefore at least $\lceil n/2 \rceil$ swaps are required. Selection Sort achieves this bound with $\Theta(n)$ swaps.

Comparison Sorts vs Linear-Time Sorts

The $\Omega(n \log n)$ bound applies only to comparison-based sorts. Algorithms that exploit properties of the data can beat this bound:

Sort	Bound	Assumption
Counting Sort	$\Theta(n + k)$	Keys in range $[0, k]$
Radix Sort	$\Theta(d(n + k))$	$d$-digit numbers
Bucket Sort	$\Theta(n)$ expected	Uniform distribution over $[0, 1)$

These are not comparison-based; they use counting, digit extraction, or hashing.

Summary

Concept	Detail
Lower bound	$\Omega(n \log n)$ comparisons
Proof technique	Decision tree model
Key inequality	$2^h \ge n!$
Stirling’s approx	$\log(n!) \approx n \log n - n \log e$
Optimal sorts	MergeSort, HeapSort (comparison-based)
Swap lower bound	$\Omega(n)$
Exceptions	Linear-time non-comparison sorts