Best-case time: comparison-based sorting on a list of size n must make n-1 comparisons (reference to proof)

Question

I am looking for a reference to a proof that for every list of size $n$ comparison-based sorting cannot make less than $n-1$ comparisons. Do you have a reference of a book that covers it (with page specification)? Or a scientific publication that covers the proof? The reference is needed for a publication.

Answer 1

Here is an easy argument that relies on the well-known lower-bound of $\log_2 n!$ on the number of comparisons needed by any comparison-based sorting algorithm (which you can find in any textbook. See, for example, Theorem 8.1 in Cormen, Leiserson, Rivest, Stein, "Introduction to Algorithms - 3rd Edition."). Then it suffices to notice that: $$ \log_2 n! \ge \log_2 2^{n-1} = n-1. $$

Alternatively, you can prove your (weaker) lower bound from scratch. Here is a possible proof:

Suppose towards a contradiction that you have a deterministic comparison-based sorting algorithm $A$ that sorts can sort a list of $n \ge 2$ elements using at most $n-2$ comparisons. If you invoke $A$ on the list any permutation $L$ of $L^* = \langle 1, 2, \dots, n\rangle$ with respect to the strict linear order of natural numbers, the output must be $L^*$.

Consider then the graph $G = (\{1, \dots, n\},E)$ in which there is an edge $(i,j)$ iff $i$ is compared with $j$ by $A$ with input $L$. Sincere there are at most $n-2$ edges, $G$ has at least two connected components. Let $C$ be the connected component of $G$ containing vertex $1$. Given $i$ and $j$ consider the strict linear order $\prec$ such that $i \prec j$ iff one of the following conditions hold (we are essentially "moving" the elements in $C$ at the end of the order):

• $i,j \in C$ and $i<j$; or
• $i,j \not\in C$ and $i<j$; or
• $i \not\in C$, $j \in C$.

The output $A$ when the input is $L$ and the considered strict linear order is $\prec$ must still be $L^*$ (since all comparisons performed by the algorithm return the same result with both $\prec$ and the linear order of the natural numbers). This contradicts the correctness of $A$.

Answer 2

Let us show a different bound, that will suffice for a "loose" bound of $n-1$. On this note, the answer above gives you the tight bound of $\Theta(n\log n)$, which is stronger than the one you are trying to prove.

$\textbf{claim:}$ To determine, via comparisons, $x_m$ is the maximum in a given set $X$, every other $x_i \in X$, for $i\neq m$ has to participate in either one of these comparisons:

• $x_i$ has been compared to $x_m$ and is lesser
• $x_i$ has been compared to $x_j$ and is lesser or equal, for some $x_j$ s.t $x_j<x_m$.

The proof is fairly straightforward; if we assume the claim is not true, we get that $x_m$ has been "found" to be the maximum, and there must be some $x_k$ that did not participate in either comparison as shown above. Hence, it is feasible $x_k > x_m$ and we cannot decide $x_m$ is the maximum.

Conclusion from the claim is that to find a maximum in a set of size $n$ will require at least $n-1$ comparisons.

I will leave it to you to finish the proof you need.

Answer 3

If $A$ is a comparison-based sorting algorithm and $L$ is any of its input lists then the comparison-graph $C_{G}(L) = (V, E_{L})$ has a set of vertices $V = \{1,\ldots,n\}$ and a set of edges $E_{L}$ consisting of the pairs $(i,j)$ for which $L[i] < L[j]$ is determined during the execution of $A$ on input list $L$.

The series of swaps executed by a comparison-based sorting algorithm $A$ on input list $L$ determines a permutation $\sigma_{L}$ which sorts $L$, i.e. $\sigma_{L}(L) = \tilde{L}$ where $\tilde{L} = [1,\ldots,n]$.

Assume by way of contradiction that a comparison-based sorting algorithm $A$ sorts a list $L$ of $n \geq 2$ elements in at most $n-2$ comparisons. Hence the edge set $E_L$ of the comparison-graph $C_{G}(L) = (V, E_L)$ has cardinality $|E_L| \leq n-2$. The comparison-graph $C_G(L)$ thus can be partitioned in two non-empty parts $G_1$ and $G_2$ between which there exists no edge connection.

Consider vertices $k = L[i] \in G_1$ and $l = L[j] \in G_2$ and two extensions of $E_L$: $E_1 = E_L \cup \{(k,l)\}$ and $E_2 = E_L \cup \{(l,k)\}$. Neither $(k,l)$ nor $(l,k)$ is in the transitive-reflexive closure $E^*$ and thus the algorithm never executes a swap on either. Moreover, $A$ executes in exactly the same way on any input list $L_1$ satisfying the relation $E_1$ and on any input list $L_2$ satisfying the relation $E_2$. Hence their computations involve exactly the same series of swaps, i.e. $\sigma_{L_1} = \sigma_{L_2}$. This contradicts the fact that $L_1$ and $L_2$ are distinct (by their definition) and hence cannot both be transformed to the same sorted output $\tilde{L}$ by the same permutation. (Note that $L$ is consistent with $E_1$ or $E_2$, hence one of the lists $L_1$ or $L_2$ could be chosen to be $L$.)