merge sort is in infinite loop

Question

I am trying to code a recursive merge sort. However, as I run the code I found out that the code does not go through the right array. Please help me solve the problem.

void merge_sort_recursive(int *arr, int left, int right) {
    int mid;
    while (left < right) { 
        mid = (left + right) / 2;
        merge_sort_recursive(arr, left, mid);
        merge_sort_recursive(arr, mid + 1, right);
        merge_recursive(arr, left, mid, right);
    }
    for (int i = 0; i < 4; i++)
        cout << arr[i] << " ";
    cout << endl;
}

void merge_recursive(int *arr, int left, int mid, int right) {
    int *buffer = new int[right + 1]; 
    int lPtr = left; 
    int rPtr = mid + 1;
    int bPtr = left; 

    while (lPtr <= mid && rPtr <= right) {
        if (arr[lPtr] < arr[rPtr]) 
            buffer[bPtr++] = arr[lPtr++];
        else
            buffer[bPtr++] = arr[rPtr++];
    }

    if (lPtr > mid) 
        for (int i = rPtr; i <= right; i++)
            buffer[bPtr++] = arr[i];
    else 
        for (int i = lPtr; i <= mid; i++)
            buffer[bPtr++] = arr[i];

    for (int i = left; i <= right; i++) 
        arr[i] = buffer[i]; 
}

user_4593267 · Answer

There are multiple problems in your code:

in function merge_sort_recursive, you should not loop while (left < right) but just proceed recursively if (left < right).
you should remove the output in merge_sort_recursive. I suppose you only have it there for debugging purposes.
in function merge_recursive you allocate a temporary array of size right + 1. This is much too large, right - left + 1 is sufficient (with adjustments on the index values).
you do not delete the temporary array, causing substantial memory leaks,
the test in the first merge loop should use <= instead of <,

The main problem is the while loop that prevents returning from the recursive calls.

Here is a modified version:

void merge_sort_recursive(int *arr, int left, int right) {
    if (left < right) { 
        int mid = (left + right) / 2;
        merge_sort_recursive(arr, left, mid);
        merge_sort_recursive(arr, mid + 1, right);
        merge_recursive(arr, left, mid, right);
    }
}

void merge_recursive(int *arr, int left, int mid, int right) {
    int *buffer = new int[right - left + 1];
    int lPtr = left;
    int rPtr = mid + 1;
    int bPtr = 0;

    while (lPtr <= mid && rPtr <= right) {
        if (arr[lPtr] <= arr[rPtr]) 
            buffer[bPtr++] = arr[lPtr++];
        else
            buffer[bPtr++] = arr[rPtr++];
    }
    /* copy the remaining elements from the left part */
    while (lPtr <= mid) {
        buffer[bPtr++] = arr[lPtr++];
    }
    /* no need to copy the remaining elements from the right part 
       because they already are at the final position */
    for (int i = 0; i < bPtr; i++) {
        arr[left + i] = buffer[i];
    }
    delete[] buffer;
}

merge sort is in infinite loop

1 Answers