Counting Inversions with merge-sort I'm doing this course: Engineering: Algorithms1 - SELF PACED Algorithms: Design and Analysis, on Stanford's website. And the first assignment asked us to count the inversions in an array.

The idea that they used was:


Break the original array in half.
Count the inversions in each half
Pass the original array through mergeSort to get the split inversions


If this is so, then I do not understand how can the mergeSort not recount the inversions from each half.

From what I thought, every time I pick the element from the right array over the element from the left array that would be an inversion. And since we work recursively into basic single elements of the array, this would also go through each of the halves when merging, therefore recounting.

Am I missing something?
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).