An inversion is a pair of places of a sequence where the elements on these places are out of their natural order.
I understood the naive approach where we take an element from 1 list and compare with all the elements of the other list. Hence making it a $\theta(n^2)$ approach.
But there is one more approach using merge sort which requires $\theta(n\log n)$ time. I failed to undertsand how to count inversion pairs from two list while merging the lists. How can it be done in $\theta(n)$ time.
Let's say we started with:
8 7 5 6 3 2 1 4
and mergesort got all the way up to two halves of the list:
5 6 7 8, 1 2 3 4
Now we want to merge. When we choose from the right half, we add the number of remaining elements on the left half to the inversion count.
For example:
We choose 1 and add 4 We choose 2 and add 4 We choose 3 and add 4 We choose 4 and add 4 Then we only choose for the left.
Prior to that, we would have had:
7 8 , 5 6 (resulting in 4)
and
2 3 , 1 4 (resulting in 2)
And at the very lowest level:
8 , 7 (1)
5 , 6 (0)
3 , 2 (1)
1 , 4 (0)
Add it all up to get 24, which is the right result.