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 <iostream>
using namespace std;
int merge(long long int arr[],int start, int mid, long long int end, int inversion){
int Arr[end-start+1];
int p=start;
int q=mid+1;
int k=0;
for(int i=start;i<=end;i++){
if(p>mid){
Arr[k++]=arr[q++];
}else if(q>end){
Arr[k++]=arr[p++];
}else if(arr[p]>arr[q])
{Arr[k++]=arr[q++];
inversion+= mid+1-p;
}
else if(arr[p]<arr[q])
Arr[k++]=arr[p++];
}
for(int i=0;i<k;i++){
arr[start++]=Arr[i];
}
return inversion;
}
int mergesort(long long int arr[],int start,long long int end,int inversion){
if(start<end){
int mid=(start+end)/2;
mergesort(arr,start,mid,inversion);
mergesort(arr,mid+1,end,inversion);
return merge(arr,start,mid,end, inversion)+merge(arr,start,mid,end, inversion); //this recursive will return the value inversion and i want to sum it but it always only return the last value of merge to the main function.
i tried like : return inversion+= merge(arr,start,mid,end, inversion)+merge(arr,start,mid,end, inversion); but still only return last value of recursive call to main. how can i return the sum value?
}
}
int main()
{ int arraysize;
cin>>arraysize;
long long int arr[arraysize];
for(int i=0;i<arraysize;i++){
cin>>arr[i];
}
int inversion=0;
inversion+=mergesort(arr,0,arraysize-1,inversion);
cout<<inversion;
return 0;
}
|
