Inversion count gives error on large inputs-CodePudding

The given code is for counting the inversions in the given array or we can say to count the number of changes to be made in an array so that it becomes sorted. Code is working fine for the inputs lower than 10**5 but above that it is giving error and I am unable to solve the error. I also use long long data type where it is required so that it can handle large inputs.

 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);
}

CodePudding user response：

The merge function is using local stack space for the variable length arrays arr1[], arr2[], and runs out of stack space for large arrays. Change the code in merge to:

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

However merge is called a lot of times for a large array, doing a lot of news and deletes. It would be better to do a one time allocation and copy to a second array, then alternate direction of merge based on level of recursion, as shown in the wiki example:

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

CodePudding user response：

here

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

you arre creating potentially large items on the stack. In other places you use the heap. You should stick to using the heap