1
$\begingroup$

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:

  1. Break the original array in half.

  2. Count the inversions in each half

  3. 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?

$\endgroup$
2
$\begingroup$

An inversion is a pair of indices $(i, j)$, with $i < j$ and $a_i > 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).

$\endgroup$
  • $\begingroup$ And is this more efficient than just counting through mergeSort? $\endgroup$ – DTek Aug 14 '18 at 10:38
  • $\begingroup$ @DTek I'm not sure what you mean by "counting through mergeSort". In the algorithm I described (which is very likely completely equivalent to the algorithm in your course) does count the inversions with mergesort. But of course not in the naive way... $\endgroup$ – Jakube Aug 14 '18 at 11:50
  • $\begingroup$ Sorry, misunderstood you! Yes this was what I was thinking. For some reason I was thinking what they meant was using another function to get the first half and the second half. Thanks for your help! $\endgroup$ – DTek Aug 14 '18 at 12:40

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.