-
Notifications
You must be signed in to change notification settings - Fork 0
/
count inversions
40 lines (40 loc) · 1.15 KB
/
count inversions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
long long int merge(long long arr[], int left, int mid, int right){
long long int cnt = 0;
vector<long long int>ans;
int l = left, r = mid+1;
while(l<=mid && r<=right){
if(arr[l] <= arr[r]){
ans.push_back(arr[l]);
l++;
}else{
cnt+=(mid -l+1);
ans.push_back(arr[r]);
r++;
}
}
while(l<=mid){
ans.push_back(arr[l]);
l++;
}
while(r<=right){
ans.push_back(arr[r]);
r++;
}
for(int i = left;i<=right;i++){
arr[i] = ans[i - left];
}
return cnt;
}
long long int mergeSort(long long arr[], int low, int high){
long long int cnt = 0;
if(low >= high) return cnt;
int mid = low + (high - low)/2;
cnt+= mergeSort(arr, low, mid);
cnt+= mergeSort(arr, mid+1, high);
cnt+= merge(arr, low, mid, high);
return cnt;
}
long long int inversionCount(long long arr[], long long n) {
// Your Code Here
return mergeSort(arr, 0, n-1);
}