A Lower Bound for Comparison-Based Sorting

We have now seen three comparison-based sorting algorithms that each run in $O(n\log n)$ time. By now, we should be wondering if faster algorithms exist. The short answer to this question is no. If the only operations allowed on the elements of a are comparisons, then no algorithm can avoid doing roughly $n\log n$ comparisons. This is not difficult to prove, but requires a little imagination. Ultimately, it follows from the fact that

$$\log(n!) = \log n + \log(n − 1) +\ldots+ \log(1) = n\log n − O(n)$$

We will start by focusing our attention on deterministic algorithms like merge-sort and heap-sort and on a particular fixed value of n. Imagine such an algorithm is being used to sort n distinct elements. The key to proving the lower bound is to observe that, for a deterministic algorithm with a fixed value of n, the first pair of elements that are compared is always the same. For example, in heap_sort(a), when n is even, the first call to trickleDown(i) is with i = n/2 − 1 and the first comparison is between elements a[n/2 − 1] and a[n − 1].

Since all input elements are distinct, this first comparison has only two possible outcomes. The second comparison done by the algorithm may depend on the outcome of the first comparison. The third comparison may depend on the results of the first two, and so on. In this way, any deterministic comparison-based sorting algorithm can be viewed as a rooted binary comparison tree. Each internal node, $u$, of this tree is labelled with a pair of indices u.i and u.j. If a[u.i] < a[u.j] the algorithm proceeds to the left subtree, otherwise it proceeds to the right subtree. Each leaf w of this tree is labelled with a permutation $w.p[0],...,w.p[n − 1]$ of $0,...,n−1$. This permutation represents the one that is required to sort a if the comparison tree reaches this leaf. That is,

$$a[w.p[0]] < a[w.p[1]] < \ldots < a[w.p[n − 1]]$$

Visual demonstration of a comparison tree

An example of a comparison tree for an array of size $n = 3$ is shown below.