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

- List the five inversions in the array $\langle 2, 3, 8, 6, 1 \rangle$.
- What array with elements from the set $\lbrace 1, 2, \ldots, n \rbrace$ has the most inversions? How many does it have?
- What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.
- 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).

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

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.

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

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
```

#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; } }