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. $(1, 5)$, $(2, 5)$, $(3, 4)$, $(3, 5)$, $(4, 5)$.

b. The array $\langle n, n - 1, \dots, 1 \rangle$ has the most inversions $(n - 1) + (n - 2) + \cdots + 1 = n(n - 1) / 2$.

c. The running time of insertion sort is a constant times the number of inversions. Let $I(i)$ denote the number of $j < i$ such that $A[j] > A[i]$. Then $\sum_{i = 1}^n I(i)$ equals the number of inversions in $A$.

Now consider the while loop on lines 5-7 of the insertion sort algorithm. The loop will execute once for each element of $A$ which has index less than $j$ is larger than $A[j]$. Thus, it will execute $I(j)$ times. We reach this while loop once for each iteration of the for loop, so the number of constant time steps of insertion sort is $\sum_{j = 1}^n I(j)$ which is exactly the inversion number of $A$.

d. We'll call our algorithm $\text{COUNT-INVERSIONS}$ for modified merge sort. In addition to sorting $A$, it will also keep track of the number of inversions.

$\text{COUNT-INVERSIONS}(A, p, r)$ sorts $A[p..r]$ and returns the number of inversions in the elements of $A[p..r]$, so $left$ and $right$ track the number of inversions of the form $(i, j)$ where $i$ and $j$ are both in the same half of $A$.

$\text{MERGE-INVERSIONS}(A, p, q, r)$ returns the number of inversions of the form $(i, j)$ where $i$ is in the first half of the array and $j$ is in the second half. Summing these up gives the total number of inversions in $A$. The runtime of the modified algorithm is $\Theta(n\lg n)$, which is same as merge sort since we only add an additional constant-time operation to some of the iterations in some of the loops.

COUNT-INVERSIONS(A, p, r)
    if p < r
        q = floor((p + r) / 2)
        left = COUNT-INVERSIONS(A, p, q)
        right = COUNT-INVERSIONS(A, q + 1, r)
        inversions = MERGE-INVERSIONS(A, p, q, r) + left + right
        return inversions

MERGE-INVERSIONS(A, p, q, r)
    n1 = q - p + 1
    n2 = r - q
    let L[1..n1 + 1] and R[1..n2 + 1] be new arrays
    for i = 1 to n1
        L[i] = A[p + i - 1]
    for j = 1 to n2
        R[j] = A[q + j]
    L[n1 + 1] = ∞
    R[n2 + 1] = ∞
    i = 1
    j = 1
    inversions = 0
    for k = p to r
        if L[i] <= R[j]
            A[k] = L[i]
            i = i + 1
        else
            inversions = inversions + n1 - i + 1
            A[k] = R[j]
            j = j + 1
    return inversions