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.