Inversion count gives error on large inputs

Question

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

You didn't post the error details. My guess is that you got a stack overflow due to the recuresive call to `mergesort`. Recuresive calls consume the stack, and when it gets too deep you get a stack overflow. — wohlstad, May 14 '22 at 03:11
Questions seeking debugging help should generally provide a [mre] of the problem, which includes a function `main` and all `#include` directives, as well as the exact input required to reproduce the problem. This allows other people to easily test your program, by simply using copy&paste. — Andreas Wenzel, May 14 '22 at 05:20
Note that in order to produce a [mre], you don't have to provide 100,000 numbers as input. You can generate this input algorithmically, for example using a random number generator. See [this answer of mine](https://stackoverflow.com/a/60908271/12149471) for an example of a function `main` which generates 1 million numbers as input and passes these numbers as input to another function, in order to test that function. — Andreas Wenzel, May 14 '22 at 05:36
10**5 elements take just 17 recursive calls. That should not overflow the stack. — Goswin von Brederlow, May 14 '22 at 10:53
First using `int` for the array size is just wrong, use at least size_t. Next `int mid = (low+high)/2;` is undefined behavior when your array exceeds about a billion elements, use `std::midpoint`. Last in `solve` better use `std::span` as argument and in `merge` and `mergesort` use iterators. — Goswin von Brederlow, May 14 '22 at 10:58
Update on the stack overflow: Except then I see `long long arr1[l1];` That will use up HUGE amounts of stack and isn't even C++, it's a compiler extension to allow VLA (variable length arrays) in C++. Usually sorting is done in-place so it doesn't use up extra memory. Windows only has 1MB stack so if `main` has a 10*5 array that's 800kB stack gone and merge will overflow the stack needing another 800kB. — Goswin von Brederlow, May 14 '22 at 11:01
@GoswinvonBrederlow - for Windows, each program's executable defines the stack size. In 64 bit mode, using Visual Studio, I've been able to build programs with 256MB of stack space. You're correct in that `long long arr1[l1];` is an issue. The merge function should use new instead. — rcgldr, May 14 '22 at 23:51
@rcgldr But 1MB is the default in msvc, right? I've seen that number mentioned for the stack on windows several times. — Goswin von Brederlow, May 14 '22 at 23:52
@rcgldr The merge function should not use new, that would be horrible. You don't want to call 1'000'000 times new to sort a 1'000'000 element array. As said the common way is to modify the data in-place. Alternatively the sort should create a result vector at the start and pass it down through the functions. — Goswin von Brederlow, May 14 '22 at 23:54
@GoswinvonBrederlow - 1MB is the default for Visual Studio, but I don't know what the default is for other compilers. The point is that it's not a Windows issue, but a instead a compiler issue. — rcgldr, May 14 '22 at 23:55
@GoswinvonBrederlow - I was trying to just fix the OP's code to not overflow the stack. I lost an edit, which I've now fixed where I recommend a one time allocation and changing direction based on level of recursion as shown in wiki example. Top down merge sort is mostly academic. Most libraries implement a stable sort using a hybrid of insertion sort and bottom up merge sort, such as timsort. — rcgldr, May 15 '22 at 00:08

rcgldr · Answer 1 · 2022-05-15T07:12:23.677

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

score 0 · Answer 2 · answered May 14 '22 at 23:55

0

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

answered May 14 '22 at 23:55

pm100

48,078
23
82
145

Inversion count gives error on large inputs

2 Answers2