B. Complete exercise 13 from chapter 1 of the textbook (page 51 in the PDF), which asks for an algorithm that counts the number of inversions in an array of length n in O(n lg n) steps. As suggested there, modify the merge sort algorithm to do this. Specify this in pseudocode.

13. An inversion in an array A[1.. n) is a pair of indices (i, j) such that i A[j]. The number of inversions in an n-element array is between 0 (if the array is sorted) and (2) (if the array is sorted backward). Describe and analyze an algorithm to count the number of inversions in an n-element array in O(nlog n) time. [Hint: Modify mergesort.]