Mergesort gives garbage value for the first element of the sorted array when executing

Question

I am implementing Mergesort using the algorithm described in "Introduction to Algorithms". However, upon every execution I get a garbage value as the first element of the sorted array. Here is the code for it:

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

void mergesort(int a[], int p, int r);

void merge(int a[], int p, int q, int r)
{
    int *left, *right;
    int i,j,k,l,n1,n2;
    n1 = q-p+1;
    n2 = r-q;
    left = malloc(sizeof(int)*(n1+1));
    right = malloc(sizeof(int)*(n2+1));
    for ( i = 0; i < n1; i++) {
        left[i] = a[p+i];
    }
    for ( j = 0; j < n2; j++) {
        right[j] = a[q+j+1];
    }
    left[n1] = INT_MAX;
    right[n2] = INT_MAX;
    i = 0;
    j = 0;
    for ( k = p; k <= r; k++) {
        if (left[i] <= right[j]) {
            a[k] = left[i];
            i++;
        }
        else {
            a[k] = right[j];
            j++;
        }
    }
    free(left);
    free(right);
    return ;
}

int main(int argc, char* argv[])
{
    int i;
    int a[] = {5,2,4,7,1,3,2,6} ;
    mergesort(a,0,sizeof(a)/sizeof(int));
    for ( i = 0; i < sizeof(a)/sizeof(int); i++) {
        printf("%d\n",a[i]);
    }
    return 0;
}

void mergesort(int a[], int p, int r)
{
    if (p < r) {
        int q;
        q = (p+r)/2 ;
        mergesort(a,p,q);
        mergesort(a,q+1,r);
        merge(a,p,q,r);
    }
}

Answer 1

It looks like you have not clearly defined the meanings of the mergesort parameters. Here, your last element is positioned one past the end of the array:

mergesort(a,0,sizeof(a)/sizeof(int));

But here,

mergesort(a,p,q);
mergesort(a,q+1,r);

Q seems to be over the last element in the array. If your code follows the first, you will be forgetting to actually sort the value q. If it follows the second, you will be attempting to sort a garbage value one past the end of the array.

Answer 2

Shouldn't

mergesort(a,0,sizeof(a)/sizeof(int));

be

 mergesort(a,0,sizeof(a)/sizeof(int)-1);

?

Considering you do

 n1 = q-p+1;

etc.

There is almost certainly an off-by-one error somewhere in here.

Answer 3

You must chose if you want to include a[r] or not. Here your choice is not consistent hence the error.

Here is a good code (I don't include a[r]):

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

void mergesort(int a[], int p, int r);

void merge(int a[], int p, int q, int r)
{
    int *left, *right;
    int i,j,k,l,n1,n2;
    n1 = q-p;
    n2 = r-q;
    left = malloc(sizeof(int)*(n1+1));
    right = malloc(sizeof(int)*(n2+1));
    for ( i = 0; i < n1; i++) {
        left[i] = a[p+i];
    }
    for ( j = 0; j < n2; j++) {
        right[j] = a[q+j];
    }
    left[n1] = INT_MAX;
    right[n2] = INT_MAX;
    i = 0;
    j = 0;
    for ( k = p; k < r; k++) {
        if (left[i] <= right[j]) {
            a[k] = left[i];
            i++;
        }
        else {
            a[k] = right[j];
            j++;
        }
    }
    free(left);
    free(right);
    return ;
}

int main(int argc, char* argv[])
{
    int i;
    int a[] = {5,2,4,7,1,3,2,6} ;
    mergesort(a,0,sizeof(a)/sizeof(int));
    for ( i = 0; i < sizeof(a)/sizeof(int); i++) {
        printf("%d\n",a[i]);
    }
    return 0;
}

void mergesort(int a[], int p, int r)
{
    if (r-p > 1) {
        int q;
        q = (p+r)/2 ;
        mergesort(a,p,q);
        mergesort(a,q,r);
        merge(a,p,q,r);
    }
}