Merge Sort: Counting Inversions Solution

carlosbf
carlosbf
Sep 9, 2018 · 2 min read

This is one of the hard problems in the sorting section of hackerrank’s interview preparation kit problem set. Link here.

The problem asks you the following: given an array of n elements
A ={a1, a2, a3, ..., an} find how many inversions exist. An inversion occurs when two different elements ai and aj are part of the array and
i < j but ai >aj . An array in increasing order has 0 inversions and an array like {2, 1, 3} has one inversion.

Solution

This problem can be solved using an enhanced version of mergesort. For an in-depth explanation read this
https://www.geeksforgeeks.org/counting-inversions/ Geeks for geeks has a much better explanation than mine. But the basic idea is that you can enhance MergeSort to count inversions. The tricky part is knowing when in MergeSort you should count the inversions. I first reviewed MergeSort and made my own implementation. Then I extended it to count inversions. You should follow the same path.

Code

FULL SOLUTION HERE

long merge(vector<int>* arr, int leftBegin, int middle, int rightEnd){  int i, j, k;  int n1, n2;  long count =0;  n1 = middle-leftBegin+1;  n2 = rightEnd - middle;  vector<int> leftArr (n1);  vector<int> rightArr(n2);  for (int i = 0; i < n1; i++)
leftArr[i]= (*arr)[i+leftBegin];
for (int j = 0; j < n2; j++)
rightArr[j]= (*arr)[j+middle+1];
i = 0; j = 0; k = leftBegin; while( i < n1 && j <n2){ if(leftArr[i] <= rightArr[j]){ (*arr)[k] = leftArr[i]; i++; }else{ (*arr)[k] = rightArr[j]; j++; count = count+ (n1-i); } k++; } while(i < n1){ (*arr)[k] = leftArr[i]; i++; k++; } while(j < n2){ (*arr)[k] = rightArr[j]; j++; k++; } return count;}long countInversions_rec(vector<int> *arr, int leftBegin, int rightEnd){ long inversions = 0; if(leftBegin >= rightEnd){ return 0; } int mid = floor( (leftBegin + rightEnd) /2 ); inversions = countInversions_rec(arr, leftBegin, mid); inversions += countInversions_rec(arr, mid+1, rightEnd); return inversions + merge(arr, leftBegin, mid, rightEnd);}long countInversions(vector<int> *arr) { int n = ( arr->size() ); return countInversions_rec(arr, 0, n-1);}
Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade