count number of inversions in an array (a variation of merge sort)

5.cpp

/*
It's a modification of merge sort
see for explanation:- http://www.geeksforgeeks.org/counting-inversions/
*/
int merge_sort(int a[], int low, int high){
  if(high > low){
    int mid = (low + high)/2;
    inv_count  = merge_sort(a, low, mid);
    inv_count += merge_sort(a, mid+1, high);
    return merge(a, temp, low, mid, high);
  }
}

int merge(int a[], int temp[], int low, int mid, int high){
  int i = low;
  int j = mid+1;
  int k = 0;
  while(i <= mid && j <= high){
    if(a[i] <= a[j]){
      temp[k++] = a[i++];
    }
    else {
      temp[k++] = a[j++];
      inv_cnt = inv_cnt + (mid - i);  // this is the bitch here.
    }
  }
  while(i <= mid) temp[k++] = a[i++];
  while(j <= high) temp[k++] = a[j++];
  for(int i=0; i<n; i++) a[i++] = temp[i++];
  return inv_cnt;
}