Since the question directly mentions the sorting algorithm name that is merge sort and we can use a modified merge sort that returns the number of inversions of an array A[1 ∶ N] in O(N log N) time.
Reference. → Cormen(3rd ed.), Chap-2, Page no-42
The key idea is to use the array index to find the number of inversions(as we know that while finding inversions two things (1: i < j, 2: A[i] >A[j] ) are of prime importance.)
we use the fact that if we replace an element by its position in the same sorted array, the inverse count will remain the same. The fact holds that the number of elements greater than a[i] for some i remains the same on the left of i. The inversion count will also thus stay the same.
Suppose we have an unsorted array(A) of negative numbers then we can copy the values from this original array to a new array(B) and perform a sorting operation on this new array.
Now search the position of all the elements of array A using binary search in B. Make the newly found position the new value of A[i]. And now we can easily check the number of inversions in the updated array A and the number of inversions will be equal to P.
Reference. ->Count Inversions (Approach 2)
For example – The array is represented as [Array values: Index]. Assuming the index is started from 1 for this example, Suppose the array was [2:1, 4:2, 6:3, 1:4, 5:5] and is having 4 inversions and now we multiply (-1) by all the values of the array and the array A becomes [-2:1, -4:2, -6:3, -1:4, -5:5]
Copying the values of array A to B and then sorting it so array B will become [-1:1, -2:2, -4:3, -5:4, -6:5]
And we can now see that ‘-1’ is having an index of ‘1’ and previously it was having an index of ‘4’. So we will save the newly found positions in array A on their respective locations with regards to their values stored in array A and array A will become [2:1, 3:2, 5:3, 1:4, 4:5 ] and now we will count the number of inversions and it will eventually be equal to 4.
So T.C. will O(n log n), and option B will be the answer.
Note – we can also use Bucket sort to sort negative numbers and in order to reduce the time of bucket sort( as the worst case of bucket sort is O(n*n)) we can sort each bucket using merge sort, which will take O(n log n).