Given an array of numbers, how do we count the number of inversions in it?
Suppose we are sorting an array of numbers in increasing order, an inversion is an ordered pair of indices (i,j) such that i < j and A[i] > A[j] .
For example consider the array {3, 2, 1, 5, 4}
The inversions are {(0,1), (0,2), (1,2), (3,4)} totaling 4.
We can always use the brute force approach of comparing all possible pairs of numbers to check if each pair is an inversion or not. This takes O(n2) time.
How do we solve this efficiently?
We can modify the merge sort procedure to count the number of inversions also!
Please check out my earlier post on Merge sort to understand how it works.
Here are the steps.
- First count the inversions in the left part
- Count the inversions in the right part
- Count the inversions if they are merged using modified merge procedure
- Adding the three counts gives the actual result
We need to change the merge procedure to count the inversions. The merge procedure works like the following.
We have two sorted arrays to merge into another array.
{1, 3, 5, 7} + {2, 4, 6, 8} = {1, 2, 3, 4, 5, 6, 7, 8}
- Take two pointers to start of the two arrays.
- Compare the two elements to see which element goes to the sorted list first.
- Increment the corresponding index.
- Repeat the above steps until we reach the end of either of them.
- Add the remaining elements if any.
While comparing the two elements if the left element is lesser than right element, we simply proceed.
If the right element is lesser than left elements, then it is also lesser than all elements to the right of left element. So increment the inversion counter accordingly.
For example
{…. 5, 9, 12, 15, …}
{…..3,….}
3 Appears in the right and 5 appears in left. So we can count all the inversions (5,3), (9,3), (12,3)… in this step itself.
Here is the C++ code which implements the above algorithm. The time complexity of this implementation is O(n log n).