Merge-sort implementation doesn't work

Question

I'm trying to implement merge sort in C using arrays, here's my code:

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

void merge(int s[], int low, int middle, int high)
{
    int i,l=0,r=0;
    int left[high/2], right[high/2];

    for(i = low; i<=middle; i++) left[i-low] = s[i];
    for(i = middle+1; i<=high; i++) right[i-middle-1] = s[i];

    i = low;
    while(l <= middle-low || r <= high - middle - 1)
    {
        if(left[l] <= right[r])
        {
            s[i++] = left[l];
            l++;
        }
        else
        {
            s[i++] = right[r];
            r++;
        }
    }
    while(l <= middle-low)
    {
        s[i++] = left[l];
        l++;
    }
    while(r <= high - middle - 1)
    {
        s[i++] = left[r];
        r++;
    }
}

void mergesort(int s[], int low, int high)
{
    int i;
    int middle;
    if(low < high){
        middle = (low + high)/2;
        mergesort(s, low, middle);
        mergesort(s, middle+1, high);
        merge(s, low, middle, high);
    }
}

int main()
{
    int nums[] = {5, 345, 1, 120, 40, 3450};
    int size = (sizeof(nums))/(sizeof(int));
    int i;
    for(i = 0; i < size; i++)
        printf("%d ", nums[i]);
    printf("\n");
    mergesort(nums, 0, size);
    for(i = 0; i < size; i++)
        printf("%d ", nums[i]);
    printf("\n");
    return 0;
}

That outputs:

5 345 1 120 40 3450 
0 1 4 5 40 120 

Which is kind of close. Could someone point out my mistakes? Thank you.

Answer 1

You access the array out of bounds at several places. Your code uses C-style ranges, which have an inclusive lower bound L and an exclusive upper bound H. Exclusive means that the upper bound H is not a valid index in the (sub-)array. A typical loop over the range look like this:

for (i = L; i < U; i++) ...

or

i = L;
while (i < U) ...

A greater-than-or-equal operator <= in such loops should make you wary, as should suprious additions or subtraction of 1. They might be correct in some cases, but they are usually consequences of inconsitent array indexing.

Let's revise your code with the C-style ranges in mind:

int left[high/2], right[high/2];

The array sizes are wrong. The left array has middle - low elements and the right array has high - middle elements. If the array size high - low is odd, you have one more element in right than in left.

for(i = low; i<=middle; i++) left[i-low] = s[i];

You mistakenly put the middle element in the left array. It is the first element of the right array.

for(i = middle+1; i<=high; i++) right[i-middle-1] = s[i];

Same here, plus you access s[high] which is one beyond the array.

i = low;
while(l <= middle-low || r <= high - middle - 1)

The conditions should have < and no -1. More importantly, the conditions should both be true, otherwise you access the subarrays out of bounds; hence the operator should be ´&&`.

    if(left[l] <= right[r])

The <= is okay, though, for once.

while(l <= middle-low)
{
    s[i++] = left[l];
    l++;
}
while(r <= high - middle - 1)
{
    s[i++] = left[r];
    r++;
}

Here, it should be < again. Also note that you access left with the index r, which is probably just a typo owed to copy and paste.

if(low < high){
    middle = (low + high)/2;
    mergesort(s, low, middle);
    mergesort(s, middle+1, high);
    merge(s, low, middle, high);
}

Here, the second call to megesort should be to middle, not to middle + 1. Because the upper bound is exclusive and the lower is not, adjacent arrays share the same bounds.

Here's a sort that works:

void merge(int s[], int low, int middle, int high)
{
    int i, l = 0, r = 0;
    int left[middle - low];
    int right[high - middle];

    for (i = low; i < middle; i++) left[i - low] = s[i];
    for (i = middle; i < high; i++) right[i - middle] = s[i];

    i = low;
    while (low + l < middle && middle + r < high) {
        if (left[l] < right[r]) {
            s[i++] = left[l];
            l++;
        } else {
            s[i++] = right[r];
            r++;
        }
    }

    while (low + l < middle) {
        s[i++] = left[l];
        l++;
    }

    while (middle + r < high) {
        s[i++] = right[r];
        r++;
    }
}

void mergesort(int s[], int low, int high)
{
    int middle;

    if (low + 1 < high) {
        middle = (low + high) / 2;
        mergesort(s, low, middle);
        mergesort(s, middle, high);
        merge(s, low, middle, high);
    }
}

The code can still be improved. The different indices for the left and right subarrays make it difficult to maintain and test the code. If you have already learned about pointer arithmetic, you can do without the low bound entirely by passing array + low and the size as new array base, as EOF has suggested in a comment.