In an array, total number of inversions depends upon the number of pairs (i, j) so that i < j and a[i] > a[j]. So a brute force algorithm is to loop through index i and count the total number of elements smaller than a[i] after index i.
Brute-force algorithm takes time O(N^2) as every time an element is compared to all other element in the array.
But by divide and conquer it can be reduced to O(N logN).
We can modify the mergesort algorithm to count the number of inversions while sorting. This takes time O(nlogn) for an array of size n.
- Divide: Divide the array of size n into two subarrays of size n/2 each.
- Conquer: Recursively compute the number of inversions in both subarrays.
- Combine: Count the number of inversions split across the two subarrays. This can be done in linear time by modifying the merge procedure of mergesort such that when it copies an element from the right subarray to the original array, it adds the number of remaining elements in the left subarray to the count of split inversions.
T(n) = O(1) + T(n/2) + T(n/2) + O(n)
= 2T(n/2) + n
= O(n logn)
