Segmentation Fault - Core Dumped in MergeSort Function

Question

Can anyone provide insight as to why the following section of code would result in a segmentation fault (core dumped) error? I am sure I have a stray pointer or something; however, I cannot find it. Any help would be appreciated. I am trying to create a MergeSort function.

int* mergesort(int* num, int n)
{
    int *left, *right;
    int middle = n/2;

    if (n <= 1)
        return num;

    //split array into two halves each with elements of 0...middle-1 and middle...n-1 correspondingly
    split(num, n, &left, &right, middle);
    left = mergesort(left, middle);
    right = mergesort(right, n-middle);

    merge(num, left, right, middle, n-middle);

    free(left);
    free(right);

    return num;
}       

void split( int* num, int n, int** left, int** right, int middle)
{

    left = &num;
    right = &num + middle;

} 

int* merge (int* num, int* left, int* right, int sizeLeft, int sizeRight)
{
    int i, j, k, n;
    i = j = k = 0;
    n = sizeLeft + sizeRight;

    while (k < n) 
    {
        if  (i < sizeLeft) 
        {
            if (j < sizeRight) 
            {
                insert(num, left, right, &i, &j, &k);
            }
            else 
            {
                append(num, left, sizeLeft, &i, &k);
            }
        }
        else 
        {
            append (num, right, sizeRight, &j, &k);
        }
    }
}

void insert(int* num, int* left, int* right, int* i, int* j, int*k)
{
    if (left[*i] < right[*j]) 
    {
        num[*k] = left[*i];
        (*i)++;
    }
    else 
    {
        num[*k] = right[*j];
        (*j)++;
    }

    (*k)++;
}

void append(int* num, int* half, int sizeHalf, int* i, int* k)
{
    while (*i < sizeHalf) 
    {
        num[*k] = half[*i];
        (*i)++; (*k)++;
    }
}

Answer 1

You do not allocate memory in the split function:

void split( int* num, int n, int** left, int** right, int middle) {
    left = #
    right = &num + middle;
}

The code above actually does not do anything useful: it modifies its arguments, period. Arguments themselves do not survive the function call.

You should instead allocate copies of the left and right halves of the array:

void split(int *num, int n, int **left, int **right, int middle) {
    *left = malloc(middle * sizeof(**left));
    memcpy(*left, num, middle * sizeof(**left));
    *right = malloc((n - middle) * sizeof(**right));
    memcpy(*right, num + middle, (n - middle) * sizeof(**right));
} 

This is not the most efficient implementation of mergesort as it uses N*log(N) space, but it should work.

A more efficient solution is to copy the array contents just before the merge phase: split could then be written as to modify the pointers to which it receives addresses:

void split(int *num, int n, int **left, int **right, int middle) {
    *left = num;
    *right = num + middle;
}

But it is really not needed as using left and right for 2 different purposes if confusing. Indeed, You need to make copies of the halves to pass to the merge function so te latter does not clobber the data as it merges in place:

mergesort(num, middle);
mergesort(num + middle, n-middle);

left = malloc(middle * sizeof(*left));
memcpy(left, num, middle * sizeof(*left));
right = malloc((n - middle) * sizeof(*right));
memcpy(right, num + middle, (n - middle) * sizeof(*right));

merge(num, left, right, middle, n-middle);

free(left);
free(right);

You do not actually need to save both halves before the merge phase: if you modify the computation of the middle point to make sure the left half is as least as long as the right half (middle = (n+1) >> 1;), you then just need to save the left half as the merge phase will not overwrite elements it has not already copied. With this method, you do not even need to append the right half as it will already be in the right place.

The functions split, insert and append should be folded into merge. Passing all these variables by reference leads to complicated, error prone and inefficient code. merge and mergesort both return int* for no real purpose, make them void.

A less important issue: the comparison in insert() should be <= to achieve stable sort (not an issue for an array of int, but useful if you generalize the algorithm to more complex elements).