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