# Counting Inversion Pair using Merge Sort

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.