Counting Inversions with merge-sort
An inversion is a pair of indices $(i, j)$, with $i &lt; j$ and $a_i &gt; a_j$.
If you separated the array into two halves, then the inversions fall into three categories:


both indices of an inversion appear in the left half -> we count those in the first recursive call
both indices of an inversion appear in the right half -> we count those in the second recursive call
$i$ is in the left half, and $j$ is in the right half.


So in the merge step, we need to make sure that we only count those inversions of the third type.

By taking the definition of inversion, this translates as follows:
For each element in the left half ($a_i$), count how many elements in the right side are smaller ($a_j$). It should be obvious, that this really counts all inversions of the third category, and that it only counts these.
This translation also gives a very native $O(n^2)$ implementation of this step.

To make this more efficient, we can use the fact that both halves are sorted after the recursive calls, and we can use two pointers so that we can accomplish this step in $O(n)$. The pointers point to the first unprocessed element in each half. Then we take the smaller one of the two unprocessed elements, and put it in our merged array. If this one is of the first half, then we can count in constant time how many were smaller than it in the second half (by looking at the index of the second pointer).