Error in C: Merge Sort implementation - memory allocation

Question

Memory allocation (rather, freeing problems) in a Merge Sort implementation in C. Here's a link to the code: http://ideone.com/UTjil7

The code is too long to be pasted here, anyway here's the main memory problem giving part:

int *MergeSort(int *A, int x, int y) //declaration
{
if(x==y) //base case, return the 1-element array itself
{
    return A;
}

else
{
    int size=1+y-x; //total no. of elements
    int half=(x+y)/2; //halving the array

    int halfsize=(size/2);
    int *A1=(int *)malloc(halfsize*sizeof(int));
    int *A2=(int *)malloc((size-halfsize)*sizeof(int)); 
    A1=MergeSort(A, x, half);           //calling MergeSort on 1st half of array
    A2=MergeSort(A, half+1, y);     //calling MergeSort on 2nd half of array


    int *C;                                 //pointer to 3rd array
    C=(int *)malloc(size*sizeof(int));
    int j=0;            //indicator for first half
    int k=0;            //indicator for 2nd half
    int i=0;            //indicator for 3rd array


    while((j<=half)&&(k<=half))         //till all the elements from either half are not exhausted
    {
        if(A1[j]<=A2[k])                    //if element of first half is smaller, put that in C
        {
            C[i]=A1[j];
            j++;
        }
        else                    //otherwise put element of second half in C
        {
            C[i]=A2[k];
            k++;
        }
        i++;                //increment indicator for C
    }
    int flag;
    if(j==(half+1))
    {
        flag=1;
    }
    else if(k==(half+1))
    {
        flag=2;
    }
    if(flag==1)         //if first half is finished
    {
        while(i<size)       //transfer all elements of second half in C
        {
            C[i]=A2[k];
            i++;
            k++;
        }

    }
    else if(flag==2) //if second half is finished
    {
        while(i<size) //transfer all elements of 1st half in C
        {
            C[i]=A1[j];
            i++;
            j++;
        }
    }


    for(int i=x;i<=y;i++) //copyback
    {
        A[x]=C[i-x];
    }
    free(A1); //Line 105
    free(A2); //Line 106
    free(C);
    return A;
}

}

It gives me Aborted(core dumped) after taking input and trying to run.

I ran the code using Valgrind. It says "invalid free" at Line 105 and 106. Help would be much appreciated!

Since you've posted only part of your code, it would be good to know which lines actually are lines 105, 106 and 26. (You can tag them with a comment) Anyway, you allocate memory for `A1` and `A2` and then re-assign the pointers to the return value of `MergeSort`, which is `A`. This gives you some surprises when writing and also introduces meory leaks, because the frashly allocated memory is no longer accessible. — M Oehm, Feb 25 '14 at 17:30
Note that you should [never cast the result of malloc in C](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc). — Paul R, Feb 25 '14 at 17:32
@M Oehm: If I write A1=MergeSort(A,0,half) without allocating memory to A1, how would that work? For example. If I take a 2 element array A[0,1], I pass pointer to A in the first call. Then MergeSort[A,0,0] and MergeSort[A,1,1] is passing parts of A and returning pointers of half the size? — Mallika, Feb 25 '14 at 17:49
You don't have to allocate memory every time you work with pointers. In another sorting algorithm, say selection sort, you wouln't allocate memory at all. You would sort the array "in place": after calling the sorting function, the array is sorted. The original unsorted array is lost. That array was already in memory, be it on the heap or on the stack. You only need to allocate memory if you need new storage. That's the case in merge sort, because you need an auxiliary array to merge the sub-arrays to. The array is only temporary, because you free it in the same function. — M Oehm, Feb 25 '14 at 17:56
Okay, so I just allocate memory for the 3rd array where I have to store the merged arrays? But I still can't figure out what is being returned if I just, without allocating, for instance, write int *A1=MergeSort(A,0,half). :| — Mallika, Feb 25 '14 at 18:05
Don't return anything; make the function `void`. In C, there are two basic ways to get results: (1) Return a value. (2) Change data that is passed by reference. Arrays are passed by reference, so you use (23) here. (You can use both, as in `scanf`. And there's also (3) Store the result in a global variable, but don't do that.) The effect or "result" if you like of the function is that the original array (or sub-array) will be sorted. — M Oehm, Feb 25 '14 at 18:10

Boklucius · Answer 1 · 2014-02-25T17:34:40.807

2

int *A1=(int *)malloc(halfsize*sizeof(int));
int *A2=(int *)malloc((size-halfsize)*sizeof(int)); 
A1=MergeSort(A, x, half);           //calling MergeSort on 1st half of array
A2=MergeSort(A, half+1, y);     //calling MergeSort on 2nd half of array

you are allocating A1, A2, and then overwriting the pointers (if I follow the recursion correctly with A)

edited Feb 25 '14 at 17:34

answered Feb 25 '14 at 17:29

Boklucius

1,896
17
19

How could it work without allocating separate space for the two arrays? – Mallika Feb 25 '14 at 17:54
It doesn't. you are modifying the original array A that you pass to MergeSort. Maybe you want to copy part of A into A1 and A2, but those lines are missing. – Boklucius Feb 25 '14 at 17:59

Error in C: Merge Sort implementation - memory allocation

1 Answers1