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)


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.