error in C using malloc : corrupted size vs prev_size

Question

I found an answer for python but I didn't understand it.

The code is a modified merge sort. It is working fine for a small number of inputs I checked upto 10. But when I run it through an online judge, when number of inputs were high (500) it gave me this error:

Error in 'a.out': corrupted size vs. prev_size: 0x0000000000d5b8b0
======= Backtrace: =========
/lib/x86_64-linux-gnu/libc.so.6(+0x777e5)[0x7f3b83a5b7e5]
/lib/x86_64-linux-gnu/libc.so.6(+0x80dfb)[0x7f3b83a64dfb]
/lib/x86_64-linux-gnu/libc.so.6(cfree+0x4c)[0x7f3b83a6853c]
a.out[0x4009d1]
a.out[0x400ac7]
a.out[0x400a87]
a.out[0x400aa4]
a.out[0x400a87]
a.out[0x400bc7]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0)[0x7f3b83a04830]
a.out[0x4005b9]
======= Memory map: ========

and it goes for another 15 lines. Why am I getting this error? Is it because of some mistake I am making during dynamic allocation of memory using malloc?

Here's my code:

#include <stdio.h>
#include <stdlib.h>

void *Merge(int *A,int l,int m,int r,int *B,int *F);
void *Merge(int *A,int l,int m,int r,int *B,int *F){
  int i=l,j=m,k=0,*C,x,y=l,z,cSize,temp,*D,*E;

  cSize = r-l;
  C = (int *) malloc (cSize * sizeof(int));
  D = (int *) malloc (cSize * sizeof(int));
  E = (int *) malloc (cSize * sizeof(int));

  while (k < cSize){
    if((j==r) || ((i!=m) && ((A[j]*B[i]) >= (A[i]*B[j])))){
        C[k] = A[i];
        D[k] = B[i];
        E[k] = F[i];
        i++;
        k++;
    }
    if((i>=m) || ((j!=r) && ((A[j]*B[i]) < (A[i]*B[j])))){
        C[k] = A[j];
        D[k] = B[j];
        E[k] = F[j];
        j++;
        k++;
    }
  }
  for(x=0;x<k;x++){
    A[y] = C[x];
    B[y] = D[x];
    F[y] = E[x];
    y++;
  }
  free(C);
  free(D);
  free(E);
}

void *MergeSort(int *A,int left,int right,int *B,int *C);
void *MergeSort(int *A,int left,int right,int *B,int *C){
  int mid,i,j,k=0,l=0,*R,*L;
  if(right - left == 1){
    A[left] = A[left];
  }
  if(right-left > 1){
    mid = (left+right)/2;

    MergeSort(A,left,mid,B,C);
    MergeSort(A,mid,right,B,C);

    Merge(A,left,mid,right,B,C);
  }
}

int main(){
  int n,i=0,newNumt,newNumo,*a,*b,*c;

  scanf("%d",&n);
  a = (int *) malloc (n * sizeof(int));
  b = (int *) malloc (n * sizeof(int));
  c = (int *) malloc (n * sizeof(int));

  for(i=0;i<n;i++){
    scanf("%d %d",&a[i],&b[i]);
    c[i]= i+1;
  }
  MergeSort(a,0,n,b,c);
  for(i=0;i<n;i++){
    printf("%d\n",c[i]);
  }

  return 0;
}

Answer 1

This is an old post, but several issues appear left unaddressed, so the following attempts to address some of those you specifically mentioned in your post.

As mentioned in the comments the nature of the issues causing your main stated problem was found by setting -Wall during compile, then running it through a debugger, with up to 20 sets of integer pairs entered upon the prompt.

Below is your complete code with several modifications. Some are only suggestions, but others are responses to compile warnings, some more important than others. These are all commented.

Addressing one of your primary questions: Why am I getting this error? Is it because of some mistake I am making during dynamic allocation of memory using malloc?:
As mentioned my @Jonathan Leffler, it is not likely a problem with memory allocation, but the attempt to access memory that has not been allocated.
The noteworthy run-time error relating to this was seen when running your unmodified code, and is marked with a comment in the Merge() function, where the index k is incremented to a value larger than it should, causing a Dereference of out-of-bounds pointer error. The quick fix was to make the two if sections mutually exclusive by adding an else to the second one. This modification does prevent the run-time error, but is not necessarily the right (or only) change needed.

One other suggestion that I did not address in the code is the selection of variable names. As written many are too cryptic and do not add readability or understanding to what the code is attempting to do. The suggestion would be to use variable names that would allow another person (or even your self, when 3 years from now you are looking at this again.) to immediately understand what the purpose of the variable is.

Read the comments for changes to understand why they are there...

#include <stdio.h>
#include <stdlib.h>

void *Merge(int *A,int l,int m,int r,int *B,int *F);
void *MergeSort(int *A,int left,int right,int *B,int *C);

int main()
{
   // int n,i=0,newNumt,newNumo,*a,*b,*c;
    int n,i=0,*a,*b,*c; //removed unused newNumt & newNumo

    printf("\nEnter number of integer pairs:\n");//user input instructions
    scanf("%d",&n);
    a = calloc (n, sizeof(int));//see comment in MergeSort for similar
    b = calloc (n, sizeof(int));//suggested change for malloc/calloc
    c = calloc (n, sizeof(int));

    for(i=0;i<n;i++)
    {
        printf("\n%d) Enter two integer values:\n", i);//user input instructions
        scanf("%d %d",&a[i],&b[i]);
        c[i]= i+1;
    }
    MergeSort(a,0,n,b,c);
    for(i=0;i<n;i++)
    {
        printf("%d\n",c[i]);
    }
    
    return 0; 
}

void *Merge(int *A, int l, int m, int r, int *B, int *F)
{
    //int i=l,j=m,k=0,*C,x,y=l,z,cSize,temp,*D,*E;    
    int i=l,j=m,k=0,*C,x,y=l,cSize,*D,*E;//removed unused z and temp

    cSize = r-l;
   // C = (int *) malloc (cSize * sizeof(int));
   // D = (int *) malloc (cSize * sizeof(int));
   // E = (int *) malloc (cSize * sizeof(int));
    C = calloc (cSize, sizeof(int)); //it is not recommended to cast the return
    D = calloc (cSize, sizeof(int)); //of malloc/calloc/realloc in C
    E = calloc (cSize, sizeof(int)); //changed malloc to calloc to initialize
                                      //variable memory to zero before use

// Only one or the other of the following two if statements should be executed per loop, 
// by running both an access violation occurs causing crash. (eg. when k is incremented twice 
// before being tested.) 
    while (k < cSize)//k is tested only once per loop...
    {
        if((j==r) || ((i!=m) && ((A[j]*B[i]) >= (A[i]*B[j]))))
        {
            C[k] = A[i];
            D[k] = B[i];
            E[k] = F[i];
            i++;
            k++;//if k == csize-1, it will be incremented to k == csize, then go into the next section
        }
        else if((i>=m) || ((j!=r) && ((A[j]*B[i]) < (A[i]*B[j])))) //added else
        {
            C[k] = A[j]; //Dereference of out-of-bounds pointer occurs here when k is too large.
            D[k] = B[j];
            E[k] = F[j];
            j++;
            k++;// ... but possibly increment twice!
        }
    }
    for(x=0;x<k;x++)
    {
        A[y] = C[x];
        B[y] = D[x];
        F[y] = E[x];
        y++;
    }
    free(C);
    free(D);
    free(E);
    
    return 0; //function prototype requires a return to quiet the warnings
              //Only void function prototypes do not require a return statement

}


void *MergeSort(int *A,int left,int right,int *B,int *C)
{
    //int mid,i,j,k=0,l=0,*R,*L;
    int mid = 0; //removed all unused variables and initialized mid
    
    if(right - left == 1)
    {
        A[left] = A[left];
    }
    if(right - left > 1)
    {
        mid = (left + right)/2; // integer rounding

        MergeSort(A, left, mid, B, C);
        MergeSort(A, mid, right, B, C);

        Merge(A, left, mid, right, B, C);
    }
    
    return 0; //function prototype requires a return to quiet the warnings
              //Only void function prototypes do not require a return statement

}