So i have been working on a merge sort method that uses generic types as input and sorts them. I'm getting an error i don't understand. Because i use generic types and need to sort 20 kk records, i must use the malloc function to dinamically allocate the arrays i use to implement the merge sort, and therefore need to free them as soon as they are not needed anymore to avoid filling up all my memory. Here is the code (i will only put the relevant piece of code):
void merge(void ** A, int a, void ** B, int b, void ** C , CompFunction compare)
{
int i,j,k;
i=0;
j=0;
k=0;
while(i < a && j < b){
if((compare(A[i],B[j])<0)){
C[k++] = A[i++];
}
else{
C[k++] = B[j++];
}
}
while(i < a){
C[k++] = A[i++];
}
while(j < b){
C[k++] = B[j++];
}
}
void merge_sort(void** A, int n, CompFunction compare)
{
int i;
void ** A1;
void ** A2;
int n1,n2;
if(n < 2)return;
n1 = n/2;
n2 = n - n1;
A1 = malloc(sizeof(sizeof(void*))*n1);
A2 = malloc(sizeof(sizeof(void*))*n2);
printf("i:%d\n",i);
for(i = 0 ; i < n2 ; i++){
A1[i] = A[i];
}
for(i = 0 ; i < n2 ; i++){
A2[i] = A[i+n1];
}
merge_sort(A1, n1, compare);
merge_sort(A2 ,n2, compare);
merge(A1, n1, A2, n2, A, compare);
free(A1);
free(A2);
}
You'll see i call a compare function in the function parameters. That's simply a function that compares various types of data to determine which one is bigger or smaller. I've tried to remove both the free() and the error no longer shows, however the code never ends running because it fills up all the memory and the swap area on the hdd. The error I get is this:
*** Error in `./exeInt': malloc(): memory corruption
(fast):0x00000000006dffa0 ***
If someone could help me i would deeply appreaciate it.
A1 = malloc(sizeof(sizeof(void*))*n1);
this is your problem, lets evaluate this first sizeof(void *), that is 8 byte(in a 64 bit system). then you do multiply it by n1 which is an int, which causes the result to evaluate to an int, therefore you get 4 bytes * n1 and not 8 bytes like i assume you want.