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

1. List the five inversions in the array $\langle 2, 3, 8, 6, 1 \rangle$.
2. What array with elements from the set $\lbrace 1, 2, \ldots, n \rbrace$ has the most inversions? How many does it have?
3. What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.
4. Give an algorithm that determines the number of inversions in any permutation of n elements in $\Theta(n\lg{n})$ worst-case time. (Hint: Modify merge sort).

1. The five inversions

$\langle 2, 1 \rangle$, $\langle 3, 1 \rangle$, $\langle 8, 6 \rangle$, $\langle 8, 1 \rangle$ and $\langle 6, 1 \rangle$.

2. Array with most inversions

It is the reversed array, that is $\langle n, n-1, \ldots , 1 \rangle$. It has $(n-1) + (n-2) + \cdots + 1 = \frac{n(n-1)}{2}$ inversions.

3. Relationship with insertion sort

Insertion sort performs the body of the inner loop once for each inversion. Due to the nature of the algorithm, on each $k$-th iteration, if $A[1..k]$ has $m$ inversions with $A[k]$, they are in $A[k-m..k-1]$ (since the elements before $k$ are sorted). Thus, the inner loop needs to execute its body $m$ times. This process does not introduce new inversions and each outer loop iteration resolves exactly $m$ inversions, where $m$ is the distance the element is "pushed towards the front of the array".

Thus, the running time is $\Theta(n + d)$, where $d$ is the number of inversions ($n$ comes from the outer loop).

4. Calculating inversions

We just modify merge sort (in exercise 2.3.2) to return the number of inversions:

MERGE-SORT(A, p, r):
  if p < r
      inversions = 0
      q = (p + r) / 2
      inversions += merge_sort(A, p, q)
      inversions += merge_sort(A, q + 1, r)
      inversions += merge(A, p, q, r)
      return inversions
  else
      return 0

MERGE(A, p, q, r)
  n1 = q - p + 1
  n2 = r - q
  let L[1..n₁] and R[1..n₂] be new arrays
  for i = 1 to n₁
      L[i] = A[p + i - 1]
  for j = 1 to n₂
      R[j] = A[q + j]
  i = 1
  j = 1
  for k = p to r
      if i > n₁
          A[k] = R[j]
          j = j + 1
      else if j > n₂
          A[k] = L[i]
          i = i + 1
      else if L[i] ≤ R[j]
          A[k] = L[i]
          i = i + 1
      else
          A[k] = R[j]
          j = j + 1
          inversions += n₁ - i
  return inversions

C code

#include <stdio.h>

int merge(int A[], int p, int q, int r) {
    int i, j, k, inversions = 0;

    int n1 = q - p + 1;
    int n2 = r - q;

    int L[n1];
    int R[n2];

    for (i = 0; i < n1; i++) L[i] = A[p + i];
    for (j = 0; j < n2; j++) R[j] = A[q + j + 1];

    for(i = 0, j = 0, k = p; k <= r; k++) {
        if (i == n1) {
            A[k] = R[j++];
        } else if (j == n2) {
            A[k] = L[i++];
        } else if (L[i] <= R[j]) {
            A[k] = L[i++];
        } else {
            A[k] = R[j++];
            inversions += n1 - i;
        }
    }

    return inversions;
}

int merge_sort(int A[], int p, int r) {
    if (p < r) {
        int inversions = 0;
        int q = (p + r) / 2;
        inversions += merge_sort(A, p, q);
        inversions += merge_sort(A, q + 1, r);
        inversions += merge(A, p, q, r);
        return inversions;
    } else {
        return 0;
    }
}