HW An inversion in an array A[1..n] is a pair of indices (i,j) such that i Aj]. The number of inversions in an n-element array is between O (if the array is sorted) and C(n, 2) (i.e., "n choose 2") (if the array is reverse-sorted) Let A[1..n] be an array of n distinct real numbers. Give a divide-and-conquer algorithm that counts the number of inversions in A using O(n log2 n) comparisons. (Hint: modify mergesort.) Your algorithm must use divide and conquer to receive credit. You may use the following test data as an example to help you understand this problem and write correct pseudocode: input output o Describe your algorithm in pseudocode. Comment your code. (3 points) o Prove that your algorithm is correct. A proof sketch, stating the main reason your algorithm works with justification, is sufficient for credit. Simply restating the steps of the algorithm will receive no credit. (1 point) o Analyze your algorithm's running time. For credit, you must analyze your pseudocode and explain how your algorithm achieves its O(n log2 n) running time on an arbitrary input of size n. (1 point) o Now suppose we are given an array A[1.. n] of n distinct real numbers that contains k inversions, i.e., k is the number of inversions in A. What is the running time of insertion sort on such an array A in terms of n and k? Explain your answer by examining the execution of insertion sort on A. (3 points)