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];
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];
for(x=0;x<k;x++){
A[y] = C[x];
B[y] = D[x];
F[y] = E[x];
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;
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];
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];
k++;// ... but possibly increment twice!
for(x=0;x<k;x++)
A[y] = C[x];
B[y] = D[x];
F[y] = E[x];
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
On my computer, ints are 4 bytes long, so n is 68.
To determine the number of elements in the array, we can divide
the total size of the array by the size of the array element.
You could do this with the type, like this:
int a[17];
size_t n = sizeof(a) / sizeof(int);
and get the proper answer (68 / 4 = 17), but if the type of
a changed you would have a nasty bug if you forgot to change
the sizeof(int) as well.
So the preferred divisor is sizeof(a[0]) or the equivalent sizeof(*a), the size of the first element of the array.
int a[17];
size_t n = sizeof(a) / sizeof(a[0]);
Another advantage is that you can now easily parameterize
the array name in a macro and get:
#define NELEMS(x) (sizeof(x) / sizeof((x)[0]))
int a[17];
size_t n = NELEMS(a);
Unless you are forced to use C, you should never use malloc. Always use new.
If you need a big chunk of data just do something like:
char *pBuffer = new char[1024];
Be careful though this is not correct:
//This is incorrect - may delete only one element, may corrupt the heap, or worse...
delete pBuffer;
Instead you should do this when deleting an array of data:
//This deletes all items in the array
delete[] pBuffer;
The new keyword is the C++ way of doing it, and it will ensure that your type will have its constructor called. The new keyword is also more type-safe whereas malloc is not type-safe at all.
The only way I could think that would be beneficial to use malloc would be if you needed to change the size of your buffer of data. The new keyword does not have an analogous way like realloc. The realloc function might be able to extend the size of a chunk of memory for you more efficiently.
It is worth mentioning that you cannot mix new/free and malloc/delete.
Note: Some answers in this question are invalid.
int* p_scalar = new int(5); // Does not create 5 elements, but initializes to 5
int* p_array = new int[5]; // Creates 5 elements
