-
Notifications
You must be signed in to change notification settings - Fork 2
/
Inversion of array
59 lines (56 loc) · 1.63 KB
/
Inversion of array
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
using namespace std;
long long _mergeSort(long long arr[], long long temp[], long long left, long long right);
long long merge(long long arr[], long long temp[], long long left, long long mid, long long right);
long long mergeSort(long long arr[], long long array_size)
{
long long temp[array_size];
return _mergeSort(arr, temp, 0, array_size - 1);
}
long long _mergeSort(long long arr[], long long temp[],long long left, long long right){
long long mid, inv_count = 0;
if (right > left) {
mid = (right + left) / 2;
inv_count += _mergeSort(arr, temp,left, mid);
inv_count += _mergeSort(arr, temp,mid + 1, right);
inv_count += merge(arr, temp, left,mid + 1, right);
}
return inv_count;
}
long long merge(long long arr[], long long temp[], long long left,long long mid, long long right){
long long i, j, k;
long long inv_count = 0;
i = left;
j = mid;
k = left;
while ((i <= mid - 1) && (j <= right)) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
}
else{
temp[k++] = arr[j++];
inv_count = inv_count + (mid - i);
}
}
while (i <= mid - 1)
temp[k++] = arr[i++];
while (j <= right)
temp[k++] = arr[j++];
for (i = left; i <= right; i++)
arr[i] = temp[i];
return inv_count;
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
long long n,count=0;
cin >> n;
long long arr[n];
for(long long i=0;i<n;i++) cin >> arr[i];
long long ans = mergeSort(arr, n);
cout << ans << endl;
}
return 0;
}