Problem 4 (2+3+5+5+7 points) Let A[1, ..., n] be an array of n distinct numbers. If i A[j], then the pair (i,j) is called a reverse pair of A. (a) List the five reverse pairs of the array (2,3, 8, 6,1). (b) Which arrays of size n with elements from the set {1, 2, ...,n} have the smallest and the largest number of reverse pairs and why? State the expressions exactly in terms of n. (c) What is the relationship between the running time of INSERTION_SORT and the number of reverse pairs in the input array? Justify your answer. (d) Modify MERGE_SORT in order to give an algorithm which determines the number of reverse pairs in an array consisting of n numbers in (n log n) worst-case time. (e) Prove the correctness and time complexity bounds for your algorithm in part (d). Problem 4 (2+3+5+5+7 points) Let A[1, ..., n] be an array of n distinct numbers. If i A[j], then the pair (i,j) is called a reverse pair of A. (a) List the five reverse pairs of the array (2,3, 8, 6,1). (b) Which arrays of size n with elements from the set {1, 2, ...,n} have the smallest and the largest number of reverse pairs and why? State the expressions exactly in terms of n. (c) What is the relationship between the running time of INSERTION_SORT and the number of reverse pairs in the input array? Justify your answer. (d) Modify MERGE_SORT in order to give an algorithm which determines the number of reverse pairs in an array consisting of n numbers in (n log n) worst-case time. (e) Prove the correctness and time complexity bounds for your algorithm in part (d)