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?