2-4 Inversions

Let $A[1..n]$ be an array of $n$ distinct numbers. If $i < j$ and $A[i] > A[j]$, then the pair $(i, j)$ is called an inversion of $A$.

a. List the five inversions in the array $\langle 2, 3, 8, 6, 1 \rangle$.

b. What array with elements from the set $\{1, 2, \ldots, n\}$ has the most inversions? How many does it have?

c. What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.

d. Give an algorithm that determines the number of inversions in any permutation of $n$ elements in $\Theta(n\lg n)$ worst-case time. ($\textit{Hint:}$ Modify merge sort).

a. The inversions are $(1,5)$, $(2,5)$, $(3,4)$, $(3,5)$, $(4,5)$. (Remember that inversions are specified by indices rather than by the values in the array.)

b. The array with elements from $\{1, 2, \ldots, n\}$ with the most inversions is $\langle n, n - 1, n - 2, \ldots, 2, 1 \rangle$. For all $1 \le i < j \le n$, there is an inversion $(i, j)$. The number of such inversions is $\binom{n}{2} = n(n - 1) / 2$.

c. Suppose that the array $A$ starts out with an inversion $(k, j)$. Then $k < j$ and $A[k] > A[j]$. At the time that the outer for loop of lines 1–8 sets $key = A[j]$, the value that started in $A[k]$ is still somewhere to the left of $A[j]$. That is, it's in $A[i]$, where $1 \le i < j$, and so the inversion has become $(i, j)$. Some iteration of the while loop of lines 5–7 moves $A[i]$ one position to the right. Line 8 will eventually drop $key$ to the left of this element, thus eliminating the inversion. Because line 5 moves only elements that are greater than $key$, it moves only elements that correspond to inversions. In other words, each iteration of the while loop of lines 5–7 corresponds to the elimination of one inversion.

d. We follow the hint and modify merge sort to count the number of inversions in $\Theta(n\lg n)$ time.

To start, let us define a merge-inversion as a situation within the execution of merge sort in which the $\text{MERGE}$ procedure, after copying $A[p..q]$ to $L$ and $A[q + 1..r]$ to $R$, has values $x$ in $L$ and $y$ in $R$ such that $x > y$. Consider an inversion $(i, j)$, and let $x = A[i]$ and $y = A[j]$ , so that $i < j$ and $x > y$. We claim that if we were to run merge sort, there would be exactly one mergeinversion involving $x$ and $y$. To see why, observe that the only way in which array elements change their positions is within the $\text{MERGE}$ procedure. Moreover, since $\text{MERGE}$ keeps elements within $L$ in the same relative order to each other, and correspondingly for $R$, the only way in which two elements can change their ordering relative to each other is for the greater one to appear in $L$ and the lesser one to appear in $R$. Thus, there is at least one merge-inversion involving $x$ and $y$. To see that there is exactly one such merge-inversion, observe that after any call of $\text{MERGE}$ that involves both $x$ and $y$, they are in the same sorted subarray and will therefore both appear in $L$ or both appear in $R$ in any given call thereafter. Thus, we have proven the claim.

We have shown that every inversion implies one merge-inversion. In fact, the correspondence between inversions and merge-inversions is one-to-one. Suppose we have a merge-inversion involving values $x$ and $y$, where $x$ originally was $A[i]$ and $y$ was originally $A[j]$. Since we have a merge-inversion, $x > y$. And since $x$ is in $L$ and $y$ is in $R$, $x$ must be within a subarray preceding the subarray containing $y$. Therefore $x$ started out in a position $i$ preceding $y$'s original position $j$, and so $(i, j)$ is an inversion.

Having shown a one-to-one correspondence between inversions and mergeinversions, it suffices for us to count merge-inversions.

Consider a merge-inversion involving $y$ in $R$. Let $z$ be the smallest value in $L$ that is greater than $y$. At some point during the merging process, $z$ and $y$ will be the "exposed" values in $L$ and $R$, i.e., we will have $z = L[i]$ and $y = R[j]$ in line 13 of $\text{MERGE}$. At that time, there will be merge-inversions involving $y$ and $L[i], L[i + 1], L[i + 2], \ldots, L[n_1]$, and these $n_1 - i + 1$ merge-inversions will be the only ones involving $y$. Therefore, we need to detect the first time that $z$ and $y$ become exposed during the $\text{MERGE}$ procedure and add the value of $n_1 - i + 1$ at that time to our total count of merge-inversions.

The following pseudocode, modeled on merge sort, works as we have just described. It also sorts the array $A$.

1
2
3
4
5
6
7
8
COUNT-INVERSIONS(A, p, r)
    inversions = 0
    if p < r
        q = floor((p + r) / 2)
        inversions = inversions + COUNT-INVERSIONS(A, p, q)
        inversions = inversions + COUNT-INVERSIONS(A, q + 1, r)
        inversions = inversions + MERGE-INVERSIONS(A, p, q, r)
    return inversions
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
MERGE-INVERSIONS(A, p, q, r)
    n[1] = q - p + 1
    n[2] = r - q
    let L[1..n[1] + 1] and R[1..n[2] + 1] be new arrays
    for i = 1 to n[1]
        L[i] = A[p + i - 1]
    for j = 1 to n[2]
        R[j] = A[q + j]
    L[n[1] + 1] = 
    L[n[2] + 1] = 
    i = 1
    j = 1
    inversions = 0
    for k = p to r
        if R[j] < L[i]
            inversions = inversions + n[1] - i + 1
            A[k] = R[j]
            j = j + 1
        else A[k] = L[i]
            i = i + 1
    return inversions

The initial call is $\text{COUNT-INVERSIONS}(A, 1, n)$.

In $\text{MERGE-INVERSIONS}$, whenever $R[j]$ is exposed and a value greater than $R[j]$ becomes exposed in the $L$ array, we increase inersions by the number of remaining elements in $L$. Then because $R[j + 1]$ becomes exposed, $R[j]$ can never be exposed again. We don't have to worry about merge-inversions involving the sentinel $\infty$ in $R$, since no value in $L$ will be greater than $\infty$.

Since we have added only a constant amount of additional work to each procedure call and to each iteration of the last for loop of the merging procedure, the total running time of the above pseudocode is the same as for merge sort: $\Theta(n\lg n)$.