Inversions

Let be an array of n distinct numbers. If and , then the pair is called an

**inversion**of .- List the five inversions of the array

- 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 elements in worst-case time. (
*Hint*: Modify merge sort.)