## 7.3 Lower Bounds for Algorithms that Remove at Most One Inversion per Comparison After each comparison, Insertion Sort either does nothing or moves the key in the *j*th slot to the (*j* + 1)st slot. By moving the key in the *j*th slot up one slot, we have remedied the fact that *x* should come before that key. However, this is all that we have accomplished. We show that all sorting algorithms that sort only by comparisons of keys, and accomplish such a limited amount of rearranging after each comparison, require at least quadratic time. We obtain our results under the assumption that the keys to be sorted are distinct. Clearly, the worst-case bound still holds true with this restriction removed because a lower bound on the worst-case performance of inputs from some subsets of inputs is also a lower bound when all inputs are considered. In general, we are concerned with sorting *n* distinct keys that come from any ordered set. However, without loss of generality, we can assume that the keys to be sorted are simply the positive integers 1, 2,…, *n*, because we can substitute 1 for the smallest key, 2 for the second smallest, and so on. For example, suppose we have the alpha input \[Ralph, Clyde, Dave\]. We can associate 1 with Clyde, 2 with Dave, and 3 with Ralph to obtain the equivalent input \[3, 1, 2\]. Any algorithm that sorts these integers only by comparisons of keys would have to do the same number of comparisons to sort the three names. A ***permutation*** of the first *n* positive integers can be thought of as an ordering of those integers. Because there are *n*! permutations of the first *n* positive integers (see [Section A.7](LiB0099.html#1323)), there are *n*! different orderings of those integers. For example, the following six permutations are all the orderings of the first three positive integers:  This means that there are *n*! different inputs (to a sorting algorithm) containing *n* distinct keys. These six permutations are the different inputs of size 3. We denote a permutation by \[*k*1, *k*2, …, *kn*\]. That is, *ki* is the integer at the *i*th position. For the permutation \[3, 1, 2\], for example,  An ***inversion*** in a permutation is a pair  For example, the permutation \[3, 2, 4, 1, 6, 5\] contains the inversions (3, 2), (3, 1), (2, 1), (4, 1), and (6, 5). Clearly, a permutation contains no inversions if and only if it is the sorted ordering \[1, 2, …, *n*\]. This means that the task of sorting *n* distinct keys is the removal of all inversions in permutation. We now state the main result of this section. Theorem 7.1****Any algorithm that sorts *n* distinct keys only by comparisons of keys and removes at most one inversion after each comparison must in the worst case do at least  and, on the average, do at least  **** Proof: To establish the result for the worst case, we need only show that there is a permutation with *n* (*n* – 1) /2 inversions, because when that permutation is the input, the algorithm will have to remove that many inversions and therefore do at least that many comparisons. Showing that \[*n*, *n* – 1, …, 2, 1\] is such a permutation is left as an exercise. To establish the result for the average case, we pair the permutation \[*kn*, *kn–1*, …, *k*1\] with the permutation \[*k*1, *k*2, …, *kn*\]. This permutation is called the ***transpose*** of the original permutation. For example, the transpose of \[3, 2, 4, 1, 5\] is \[5, 1, 4, 2, 3\]. It is not hard to see that if *n* > 1, each permutation has a unique transpose that is distinct from the permutation itself. Let  Given a permutation, the pair (*s*, *r*) is an inversion in either the permutation or its transpose but not in both. Showing that there are *n* (*n* – 1) /2 such pairs of integers between 1 and *n* is left as an exercise. This means that a permutation and its transpose have exactly *n* (*n* – 1) /2 inversions between them. So the average number of inversions in a permutation and its transpose is  Therefore, if we consider all permutations equally probable for the input, the average number of inversions in the input is also *n* (*n* – 1) /4. Because we assumed that the algorithm removes at most one inversion after each comparison,on the average it must do at least this many comparisons to remove all inversions and thereby sort the input. Insertion Sort removes at most the inversion consisting of *S* \[*j*\] and *x* after each comparison, and therefore this algorithm is in the class of algorithms addressed by [Theorem 7.1](#ch07ex03). It is slightly more difficult to see that Exchange Sort and Selection Sort are also in this class. To illustrate that this is the case, we present an example using Exchange Sort. First, recall that the algorithm for Exchange Sort is as follows: ``` void exchangesort (int n, keytype S[]) { index i, j; for (i = 1; i <= n - 1; i++) for (j = i + 1; j <= n; j++) if (S[j] < S[i]) exchange S[i] and S[j]; } ``` Suppose that currently the array *S* contains the permutation \[2, 4, 3, 1\] and we are comparing 2 with 1. After that comparison, 2 and 1 will be exchanged, thereby removing the inversions (2, 1), (4, 1), and (3, 1). However, the inversions (4, 2) and (3, 2) have been added, and the net reduction, in inversions is only one. This example illustrates the general result that Exchange Sort always has a net reduction of at most one inversion after each comparison. Because Insertion Sort's worst-case time complexity is *n* (*n* – 1) /2 and its average-case time complexity is about *n*2/4, it is about as good as we can hope to do (as far as comparisons of keys are concerned) with algorithms that sort only by comparisons of keys and remove at most one inversion after each comparison. Recall that Mergesort ([Algorithms 2.2](LiB0016.html#158) and [2.4](LiB0016.html#169)) and Quicksort ([Algorithm 2.6](LiB0018.html#177)) have time complexities that are better than this. Let's reinvestigate these algorithms to see how they differ from ones such as Insertion Sort.