反转计数在大输入时给出错误

Question

给定的代码用于计算给定数组中的反转，或者我们可以说是计算要在数组中进行的更改的数量，以便它被排序。代码对于低于10**5的输入工作正常，但高于此，它给出错误，我无法解决错误。我还在需要的地方使用long long数据类型，以便它可以处理大的输入。

long long merge(long long arr[], int low, int mid, int high){
long long count = 0;
int l1 = mid-low+1;
int l2 = high - mid;
long long arr1[l1];
long long arr2[l2];
for(int i=0;i<l1;i++){
arr1[i] = arr[low+i];
}
for(int i=0;i<l2;i++){
arr2[i] = arr[mid+1+i];
}
int i=0, j=0, k=low;
while(i!=l1 and j!=l2){
if(arr1[i]<arr2[j]){
arr[k++] = arr1[i++];
}
else{
count+=l1-i;
arr[k++] = arr2[j++];
}
}
while(i<l1)
arr[k++] = arr1[i++];
while(j<l2)
arr[k++] = arr2[j++];

return count;
}
long long mergesort(long long arr[], int low, int high){
long long count = 0;
if(low<high){
int mid = (low+high)/2;
count+=mergesort(arr, low, mid);
count+=mergesort(arr, mid+1, high);
count+=merge(arr, low, mid, high);
}
return count;
}
long long solve(long long *arr, int n){
if(n==1) return 0;
return mergesort(arr,0, n);
}

Answer 1

合并函数使用本地堆栈空间用于可变长度数组arr1[]， arr2[]，并且耗尽了大型数组的堆栈空间。将merge中的代码更改为:

long long * arr1 = new long long[l1];
long long * arr2 = new long long[l2];
// ...
delete [] arr2;
delete [] arr1;
return count;     // existing code

然而，对于一个大数组，merge被调用了很多次，做了很多新闻和删除。最好是进行一次分配并复制到第二个数组，然后根据递归级别选择合并方向，如wiki示例所示:

https://en.wikipedia.org/wiki/Merge_sort Top-down_implementation

Answer 2

here

long long arr1[l1];
long long arr2[l2];

您正在堆栈上创建可能较大的项。在其他地方使用堆。您应该坚持使用堆