i have seen that many accpeted codes has a temp array passed to merge function but not getting what is its use? Can someone explain what is the use of that.
https://www.codechef.com/viewsolution/32139867
#include <bits/stdc++.h>
using namespace std;
vector ar;
long long counter=0;
void merge(int l, int mid, int r) {
long long left[mid-l+1]; long long n1=mid-l+1;
long long right[r-mid]; int n2=r-mid;
int k=l;
for(int i=0;i<n1;i++)
left[i]=ar[l+i];
for(int i=0;i<n2;i++)
right[i]=ar[mid+i+1];
long long i=0, j=0;
while(i<n1 && j<n2){
if(left[i]<right[j])
ar[k++]=left[i++];
else{
counter+=(n1-i);
ar[k++]=right[j++];
}
}
while(i<n1){
ar[k++]=left[i++];
}
while(j<n2){
ar[k++]=right[j++];
}
}
void merge_sort(int i, int j) {
if(i<j) {
int mid=i+(j-i)/2;
merge_sort(i, mid);
merge_sort(mid+1, j);
merge(i, mid, j);
}
}
int main() {
int n; cin >> n;
for(int i=0;i<n;i++){
long long int x; cin >> x;
ar.push_back(x);
}
merge_sort(0, n-1);
cout << counter << endl;
}