Let A0n 1 be an array of n real numbers A pair Ai Aj is sai

Let A[0..n - 1] be an array of n real numbers. A pair (A[i], A[j]) is said lo be an inversion if these numbers are out of order, i.e., i A[j]. Design an O(n log n) algorithm for counting the number of inversions.

Solution

We can use a Programming paradigm called Divide and Conquer where we can use Merge Sort to solve this Problem.
Let us go into more details
Merge Sort divides the array into left and right subarray and the final step is the Merge Step (where we can count the inversion , lets see How )

Consider this at any random Merge step at left and right subarray
A : 9, 15, 70 B: 20 40 100
During the Merge step into Final MergeD Array C
For Example when 70 is added into the final merged array, It is inverted with all the elements less than 70 , for example 20 and 40 here, so slight modification in the merge Stepo can give us the number of inversion in an array.

Hence using the Time Complexity of O(n log n) we can achieve this.