CODEWITHSUNDEEP
c++calgorithmmalloc
ratkke
ratkke

Reputation: 469

incorrect checksum for freed object on large input

I've written a program which computes the number of inversions in a .txt file (first number - amount of numbers, than go numbers themselves). On small input (5 or 10 numbers) it works fine, but when the input is 100,000 numbers (and each number less than 100,000) I get the following error:

incorrect checksum for freed object - object was probably modified after being freed.
*** set a breakpoint in malloc_error_break to debug***

Here is the code:

#include <stdio.h>

long int merge(int *arr, const int start, const int half, const int end)
{
        int s=start;
        int i=0;
        int cinv=0;
        int j=half+1;
        int* barr = new int[end+start-1];

        while((s<=half)&&(j<=end)){
                if(arr[s]<=arr[j]){
                        barr[i]=arr[s];
                        s++;

                }
                else{
                        barr[i]=arr[j];
                        j++;
                        cinv++;
                }
                i++;
        }

        if(s>half){
                for(int k = j;k<=end;k++){
                        barr[i]=arr[k];
                        i++;
                }
        }
        else{
                for(int k=s;k<=half;k++){
                        barr[i]=arr[k];
                        i++;
                }
        }

        for(int k=0;k<=end-start;k++) {
                arr[k+start]=barr[k];
        }
        delete[] barr;
        return cinv;
}

long int mergesort(int* arr, int start, int end){
    int half=(start+end)/2;
    long int cinv=0;

    if (start<end){
        cinv+=mergesort(arr, start, half);
        cinv+=mergesort(arr, half+1, end);
        cinv+=merge(arr, start, half, end);
        return cinv;
    }

    return cinv;
}

int main(){
    int len;
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    scanf("%d", &len);
    int *arr= new int[len];

    for (int i=0; i<len; i++){
        scanf("%d", &arr[i]);
    }

    long int cinv=mergesort(arr, 0, len-1);

    printf("\nInversions with merge=%ld", cinv);

    delete [] arr;
    return 0;
}

Thanks in advance for your help.

Upvotes: 0

Views: 109

Answers (1)

M Oehm
M Oehm

Reputation: 29126

The dimension of your temporary array in merge,

int* barr = new int[end+start-1];

is not correct. When you call merge with start == 0 and end == 1, this will yield an array dimension of 0. At the other end of the array, it will allocate twice as much memory as needed. Change this to:

int* barr = new int[end - start + 1];

What allocating zero bytes does, is implementation-defined. Your program crashes reliably on my Linux platform even with small input arrays.

Upvotes: 2

Related Questions