program crashed

[June Ye]

Hi,

I was trying to write mesh sort algorithm in C++.
However my program crashed when it runs.

Attached is the code.

#include <iostream>
 
using namespace std;
 
 
int* merge(int a[], int b[], int size1, int size2)
{
 
    int *value = (int*)malloc(size1+size2);
    int i, j, k;
    i=j=k=0;
 
    while(i < size1 || j < size2){
      if(a[i] < b[j])
         value[k++] = a[i++];
      else 
         value[k++] = b[j++];
    }
    while(i < size1 )
         value[k++] = a[i++];
    while(j < size2)
         value[k++] = b[j++];
 
    free(a);
    free(b);
 
    return value;
 
}
 
int* mergeSort(int* input, int start, int end)
{
 
      if(start >=end ){
        return (input+start);
      }
 
      int *a = mergeSort(input, start, (start+end)/2 );
      int *b = mergeSort( input, (start+end)/2+1, end);
 
      int size1 = (end-start)/2+1;
      int size2 = (end-start)/2+1;
 
      return merge(a, b, size1, size2);
 
}
 
int main()
{
    int input[] = {7,9,2,6,1,4,5,8};
    int * output;
    output = mergeSort(input, 0, 7);
 
    for(int j = 0; j < 7; j++)
      cout<< *(output+j);
 
    system("pause");
 
    return 0;
 
 
}
 

I assume it is because of the allocating the memory for storing the value.

I appreciate if someone can help to solve this problem...

[Banfa]

You mean and not or at line 13.

Line 24 and 25, freeing data that has been allocated elsewhere is mildly strange since you can not be sure how it was allocated.

mergeSort: Line 35 you return whatever input points at; at line 44 you return the result of merge which is an malloc'd buffer. Both of these get passed to merge at some point which assumes they are malloc'd and frees them. However you have no guarantee that input is malloc'd since this function is called externally and in fact the first time it is called from main you pass a pointer to a buffer on the stack that you subsequently try too free.

When you call mergeSort you have no idea if the returned value is a malloc'd buffer or a buffer of whatever type you passed in.


Line 9: when you malloc data ALWAYS check that the returned pointer value is not NULL before you try to use it.

[June Ye]

Hi Banfa,

Thank you very much for your response.

>You mean and not or at line 13.

That's correct. I made a mistake.

>Line 24 and 25, freeing data that has been allocated elsewhere is mildly strange since you can not be sure how it was allocated.

That's true. However when I omit that part, the program crashed earlier... Not sure how to correct that part.
I know the allocating memory part and freeing it is messed up. Do you have any suggestion about how to correct it?

Thanks a lot!

[June Ye]

Hi Banfa,

Here is the working program.
Thanks a lot!

#include <iostream>
 
using namespace std;
 
 
int* merge(int a[], int b[], int size1, int size2)
{
 
    int *value = (int*)malloc((size1+size2)*sizeof(int));
    int i, j, k;
    i=j=k=0;
 
    while(i < size1 || j < size2){
      if(a[i] < b[j])
         value[k++] = a[i++];
      else 
         value[k++] = b[j++];
    }
    while(i < size1 )
         value[k++] = a[i++];
    while(j < size2)
         value[k++] = b[j++];
 
    return value;
 
}
 
int* mergeSort(int* input, int start, int end)
{
 
      if(start >=end ){
        return (input+start);
      }
 
      int *a = mergeSort(input, start, (start+end)/2 );
      int *b = mergeSort( input, (start+end)/2+1, end);
 
      int size1 = (end-start)/2+1;
      int size2 = (end-start)/2+1;
 
      int* result = merge(a, b, size1, size2);
      free (a);
      free (b);
      return result;
 
}
 
int main()
{
    int input[] = {7,9,2,6,1,4,5,8};
    int * output;
    output = mergeSort(input, 0, 7);
 
    for(int i = 0; i < 8; i++)
      cout<< *(output+i);
 
    system("pause");
 
    return 0;
 
}