1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ You can do better: You must make at least n-1 comparisons to sort any list of n elements. $\endgroup$
    – gnasher729
    Dec 6 '21 at 17:17
  • $\begingroup$ This is the intention of the question. Is there a language issue? "A sorting algorithm cannot make less than n-1 comparisons on every list of size n" is mentioned. This is equivalent to "you must at least make n-1 comparisons to sort any list of n " ? $\endgroup$
    – Michel
    Dec 6 '21 at 17:26
  • $\begingroup$ I think the way you phrase it would be interpreted by most people as "there is no sorting algorithm which performs less than n-1 comparisons in the worst case over all lists of size n". If you move "every list of size n" to the beginning of the sentence the intended meaning becomes clear: "For every list of size n, there is no sorting algorithm which performs less than n-1 comparisons". Different order of the quantifiers. $\endgroup$
    – Tassle
    Dec 8 '21 at 8:14
  • $\begingroup$ Adjusted. Thanks. $\endgroup$
    – Michel
    Dec 8 '21 at 15:41
1
$\begingroup$

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$.

$\endgroup$
14
  • $\begingroup$ Regarding the first lower bound (log(n!)). This bound holds for the average-case time and the worst-case time, but not per input. Algorithms can use n-1 comparisons per input. For instance, insertion sort on the sorted list. I don't understand the full gist of your second argument. It makes sense up to the two components. After that the point of the newly introduced order is not clear. What does it mean to move the elements in C at the end of the order? $\endgroup$
    – Michel
    Dec 1 '21 at 16:28
  • $\begingroup$ My second argument shows that you need $n-1$ comparisons on every input. Moving the element of $C$ at the end of the order is just an intuitive explanation. It's meaning is formally defined by the order relation $\prec$. Essentially all elements of $C$ compare larger than all elements not in $C$. The order between two elements in $C$ is not affected. The order between two elements not in $C$ is not affected. $\endgroup$
    – Steven
    Dec 1 '21 at 17:43
  • $\begingroup$ Is your concluding argument (to obtain the contradiction) that the output of this revised order cannot be a sorted list? If so, on what basis? I can see intuitively that the given new order (or its opposite version where all elements in C are smaller than those not in C) give rise to the same computation path. Invoking the argument that two distinct input lists must give rise to distinct leaves in the decision tree seems circular in that it relies on the result we are trying to prove. Perhaps I'm missing something. $\endgroup$
    – Michel
    Dec 1 '21 at 18:57
  • $\begingroup$ Sorting $L$ with respect to $<$ must yield the same output as sorting $L$ with respect to $\prec$. However $<$ and $\prec$ cannot be the same linear order. This means that at least one of the two executions of the algorithm is returning the wrong output, i.e., the algorithm is not correct. (In particular $\prec$ must differ from $<$ since $1$ cannot be the smallest element w.r.t. $\prec$, but it is the smallest element w.r.t. $<$). Notice that $\prec$ needs to place the elements in $C$ after those not in $C$ (and not the other way around) otherwise $<$ and $\prec$ might coincide. $\endgroup$
    – Steven
    Dec 1 '21 at 19:05
  • $\begingroup$ The correct output with input $L$ and $<$ is $L^*$. The correct output with input $L$ and $\prec$ cannot be $L^*$ (since $\prec$ differs from $<$). The obtained output with input $L$ and $<$ is some permutation $L'$ of $L^*$ (possibly the identity permutation). The obtained output with input $L$ and $\prec$ must also be $L'$ (this is just using the fact that observing the same comparison results with the same input leads to the same output leaf in the decision tree). This is enough to derive a contradiction. $\endgroup$
    – Steven
    Dec 1 '21 at 19:19
2
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Why refer to a maximum when the question is about general comparison-based sorting algorithms which need not sort by determining the maximum value in a list? $\endgroup$
    – Michel
    Dec 1 '21 at 16:21
  • 1
    $\begingroup$ A comparison-based sorting algorithm that uses at most $c$ comparison implies the existence of a comparison-based maximum-finding algorithm that uses at most $c$ comparisons. Therefore a lower bound on the number of comparisons needed to find the maximum implies a corresponding lower bound on the number of comparisons needed to sort. $\endgroup$
    – Steven
    Dec 1 '21 at 18:00
  • $\begingroup$ Ok. That argument works $\endgroup$
    – Michel
    Dec 1 '21 at 18:43
  • 1
    $\begingroup$ I can find the maximum of an array by sorting the array and taking the last element. Therefore sorting is at least as hard as finding the largest element. $\endgroup$
    – gnasher729
    Dec 2 '21 at 0:01
  • $\begingroup$ I respectfully disagree with the statement "the other one [answer] offered has holes in it". $\endgroup$
    – Steven
    Dec 5 '21 at 19:18
0
$\begingroup$

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$.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.