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 of the array \(\{2, 3, 8, 6, 1\}\).

\[(1, 5), (2, 5), (3, 4), (3, 5), (4, 5)\]

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

The array \(\{n, n-1,...,1\}\) has \(\sum\limits_{i=1}^{n-1}n\) inversions.

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

Considering INSERTION-SORT as presented on page 26, the actions within the while loop on lines 5-7 will be taken a number of times equal to the amount of inversions in the input array \(A\). This means that the number of inversions is a constant factor of the running time of INSERITON-SORT.

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

Modify the MERGE procedure to count inversions every time we select a value from the \(R\) array. Selecting a value from the \(R\) array indicates that all remaining values in the \(L\) array are greater than our selected value thus each element in the \(L\) array at the time of selection represents an inversion. Since the overall size of \(L\) is \(n₁\), and the position of the currently ‘showing’ value on the \(L\) array is \(i\), the number of remaining elements at the time of selection is \(n₁ - i + 1\). Lines 16 and 23 of INVERSION-MERGE below represent the points where we select a value from the \(R\) array, and so that is where we record our inversion counts.

INVERSION-MERGE(A, p, q, r)

01 n₁ = q - p + 1

02 n₂ = r - q

03 Let L[1 . . n₁] and R[1 . . n₂] be new arrays

04 for i = 1 to n₁

05      L[i] = A[p + i - 1]

06 for j = 1 to n₂

07      R[j] = A[q + j]

08 i = 1

09 j = 1

10 for k = p to r

11      if j > n₂

12          A[k] = L[i]

13          i = i + 1

14      else if if i > n₁

15          A[k] = R[j]

16          inversions += n₁ - i + 1

17          j = j + 1

18      else if L[i] ≤ R[j]

19          A[k] = L[i]

20          i = i + 1

21      else

22          A[k] = R[j]

23          inversions += n₁ - i + 1

24          j = j + 1