❓ Question
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$.
- List the five inversions of the array $<2, 3, 8, 6, 1>$
- What array with elements from the set {1, 2, …. n } 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 on $n$ elements in $\Theta(nlgn)$ worst-case time. (Hint: Modify merge sort.)