Why Is Comparison Sorting Bound by O(n log n)?

The O(n log n) lower bound is a fundamental limit for comparison-based sorting algorithms in classical computing because of how much information each comparison can reveal. Any algorithm that determines the sorted order of elements solely by comparing pairs of items must distinguish between all possible initial arrangements of the input. Because each comparison only yields a binary outcome, a minimum number of comparisons is mathematically required to identify the single correct permutation, regardless of how clever the algorithm is.

The Decision Tree Model

To prove this lower bound, computer scientists model any comparison-based sorting algorithm as a binary decision tree. Each internal node in the tree represents a single comparison between two elements, such as \(a_i \le a_j\). The two branches leaving the node correspond to the two possible outcomes: true or false.

The leaves of the decision tree represent the final sorted permutations produced by the algorithm. For an input array of \(n\) distinct elements, there are \(n!\) possible initial orderings. Since a valid sorting algorithm must be able to sort any of these orderings, the decision tree must have at least \(n!\) leaves.

Calculating the Minimum Height

In a binary tree, the maximum number of leaves a tree of height \(h\) can have is \(2^h\). The height \(h\) corresponds to the worst-case number of comparisons the algorithm must perform. Therefore, for a decision tree to have at least \(n!\) leaves, its height must satisfy the inequality:

\[2^h \ge n!\]

Taking the base-2 logarithm of both sides gives the minimum worst-case number of comparisons:

\[h \ge \log_2(n!)\]

Applying Stirling's Approximation

To express \(\log_2(n!)\) in asymptotic notation, we can use Stirling's approximation for factorials, or a simpler bounding argument. For \(n!\) itself, we know that at least half of the terms in the product \(n \times (n-1) \times \dots \times 1\) are greater than or equal to \(n/2\). Thus:

\[n! \ge \left(\frac{n}{2}\right)^{n/2}\]

Taking the logarithm of both sides yields:

\[\log_2(n!) \ge \frac{n}{2} \log_2\left(\frac{n}{2}\right) = \Omega(n \log n)\]

This proves that in the worst case, any comparison-based sorting algorithm must perform at least \(\Omega(n \log n)\) comparisons. Algorithms like Merge Sort and Heapsort achieve this bound, making them asymptotically optimal.

Bypassing the Lower Bound

The \(\Omega(n \log n)\) lower bound applies strictly to algorithms that rely only on pairwise comparisons. Non-comparison sorting algorithms, such as Counting Sort, Radix Sort, and Bucket Sort, can achieve linear time complexity \(O(n)\) under specific conditions. They bypass the decision tree limit by using additional information about the keys, such as their integer values or digit representations, to place elements directly into their final positions without comparing them to one another.