Let S be an array of n elements on which a total order relation is defined. An inversion in S is a pair of indices i and j such that i < j but S[i] > S[j]. Write an Count-inversion(S) algorithm that runs in O(n log n ) time for determining the number of inversions in S. The beginning index in S is 1, i.e. S[1 .. n].

Hint: Try to modify the merge-sort algorithm to solve it.