You are viewing a single comment's thread. Return to all comments →
Can anyone help with this? I'm getting output 5 where I should get 4 in the 2nd sample.
long long merge(vector<int> arr, int l, int h){ int aux[h-l+1]; int mid = (l+h)/2; int i=l, j=mid+1, k=0, count=0; while(i<=mid&&j<=h){ if(arr[j]<arr[i]){ aux[k] = arr[j]; j++; count+=mid-i+1; } else{ aux[k] = arr[i]; i++; } k++; } while(i<=mid){ aux[k] = arr[i]; i++; k++; } while(j<=h){ aux[k] = arr[j]; j++; k++; } k=0; for(int x=l;x<=h;x++){ arr[x] = aux[k]; k++; } return count; } long long mergeSort(vector<int> arr, int lo, int hi){ if(lo>=hi) return 0; int mid = (lo+hi)/2, count=0; count+=mergeSort(arr, lo, mid); count+=mergeSort(arr, mid+1, hi); count+=merge(arr, lo, hi); return count; } long long count_inversions(vector<int> a) { return mergeSort(a, 0, a.size()-1); }
Seems like cookies are disabled on this browser, please enable them to open this website
Merge Sort: Counting Inversions
You are viewing a single comment's thread. Return to all comments →
Can anyone help with this? I'm getting output 5 where I should get 4 in the 2nd sample.