merge sorting does not reach the last element

Question

If you pass the array size to the function as the index of the last element, then everything works as it should. But if you pass the size - 1, then the sorting does not reach the last element. What is the problem?

void merge(int *array, int start, int middle, int end)
{
    int i, j, k;
    int leftpoint = middle - start;
    int rightpoint = end - middle;

    if (leftpoint == 0 || rightpoint == 0)
        return;

    int leftArray[leftpoint];
    int rightArray[rightpoint];

    for (i = 0; i < leftpoint; i++) {
        leftArray[i] = array[start + i];
    }

    for (j = 0; j < rightpoint; j++) {
        rightArray[j] = array[middle + j];
    }

    i = 0;
    j = 0;

    for (k = start; k < end; k++) {
        if (j == rightpoint || (i < leftpoint && leftArray[i] <= rightArray[j])) {
            array[k] = leftArray[i];
            i++;
        } else {
            array[k] = rightArray[j];
            j++;
        }
    }
}

void mergeSort(int *arr, int start, int end)
{
    int middle;
    if (end - start > 1) {
        middle = start + (end - start) / 2;

        mergeSort(arr, start, middle);
        mergeSort(arr, middle, end);
        merge(arr, start, middle, end);
    }
}

user_4593267 · Answer

Passing the index past the last element for right is idiomatic in C. Many books illustrate a different API, passing the index of the last element. While this would be consistent for 1 based arrays, it cannot reliably represent empty arrays and leads to confusing +1 and -1 adjustments. The posted code does not have this shortcoming and seems correct. It should be called this way:

int array[] = { ... };
int len = sizeof(array) / sizeof(*array);
mergeSort(array, 0, len);

If you observe that merge sorting does not reach the last element, you probably pass the index to the last element to the initial call instead of the number of elements.

Here are some remarks about your implementation:

the index arguments should have type size_t.
if merge is only called from mergeSort, itself called with consistent positive arguments start and end with start <= end, neither leftpoint nor rightpoint can be 0, so the test if (leftpoint == 0 || rightpoint == 0) return; is redundant.
saving the elements from mid to right is unnecessary as they cannot be overwritten before they are copied.
using temporary arrays defined locally with automatic storage can cause a stack overflow for moderately large arrays.

Here is a modified version:

void merge(int *array, size_t start, size_t middle, size_t end) {
    int leftpoint = middle - start;
    int leftArray[leftpoint];

    for (size_t i = 0; i < leftpoint; i++) {
        leftArray[i] = array[start + i];
    }

    for (size_t i = 0, j = middle, k = start; i < leftpoint;) {
        if (j == end || (i < leftpoint && leftArray[i] <= array[j])) {
            array[k++] = leftArray[i++];
        } else {
            array[k++] = array[j++];
        }
    }
}

void mergeSort(int *arr, size_t start, size_t end) {
    if (end > start + 1) {
        size_t middle = start + (end - start) / 2;

        mergeSort(arr, start, middle);
        mergeSort(arr, middle, end);
        merge(arr, start, middle, end);
    }
}

merge sorting does not reach the last element

1 Answers