Error in C using malloc: malloc.c:2451:sYSMALLOc "Assertion Failed"

Question

I'm a beginner in C and am having memory allocation problems. I checked the related discussions. I should probably use Valgrind, but till the time I learn how to use that, I'm posting the problem here.

Here's a link to a Merge Sort code I made. http://ideone.com/utEzoq

However, the main problem seems to be in the following section:

void main()
{
     MergeSort(list, 0, n-1) //calling function on pointer to array of integers
}

int *MergeSort(int *A, int x, int y) //declaration
{
if(x==y)
{
    return A;
}

else
{
    int size=1+y-x;
    int half=(x+y)/2;

    MergeSort(A, x, half);  
    MergeSort(A, half+1, y);    


    int *C;
    C=(int *)malloc(size*sizeof(int));
    int j=x;
    int k=half;
    int i=0;


    while((j<=half)||(k<=y))            
    {
        if(A[j]<=A[k])
        {
            C[i]=A[j];
            j++;
        }
        else
        {
            C[i]=A[k];
            k++;
        }
        i++;
    }


    if(j==(half+1))
    {
        while(i<size)
        {
            C[i]=A[k];
            i++;
            k++;
        }
    }
    else if(k==(y+1))
    {
        while(i<size)
        {
            C[i]=A[j];
            i++;
            j++;
        }
    }

    return C;
}

The error however arises with different kinds of inputs. When I entered a reverse sorted and sorted array, it returned the output in the order of input. And random numbers give the malloc "Assertion Failed" error.

Help would be much appreciated.

Answer 1

your problem

void main()

to

int main()

,

int k=half;

to

int k=half+1;

,

while((j<=half)||(k<=y)) 

to

while((j<=half)&&(k<=y))

,

return C;

to

for(i=0;i<size;++i){
    A[x+i]=C[i];
}
free(C);
return A;

Answer 2

You write to elements of C that are beyond the length of the array in your first while loop, thereby probably corrupting information that malloc and free use internally.

The whole implementation has errors. For example, you call the sorting function recursively and allocate auxiliary memory with every call. You return the allocated buffer, but never do anything with it, let alone free it. The sorting function doesn't sort, because the sorted data is (supposedly) in C, which you ignore. You effectively print out A.

Edit: There's no need to learn Valgrind. Install it, compile your program with -g, then run your program with Valgrind. In addition to your output, you'll get error and warning messages that state clearly where what kind of memory violation occurs. Install Valgrind now and make a habit of using it - it will save you time in the future.