Can not understand what's going wrong in my merge sort algo

Question

Here is my code:

#include <iostream>

using namespace std;

int arr[] = { 6, 1, 9, 6, 4, 7, 3 };
int n = 7;

void merge(int l, int mid, int r) {
    int n1 = mid - l + l;
    int n2 = r - mid;
    int arr1[n1], arr2[n2];

    for (int i = 0; i < n1; i++) {
        arr1[i] = arr[l + 1];
    }

    for (int i = 0; i < n1; i++) {
        arr1[i] = arr[mid + 1 + i];
    }

    int i = 0, j = 0, k = l;

    while (i < n1 && j < n2) {
        if (arr1[i] <= arr2[j]) {
            arr[k] = arr1[i];
            i++, k++;
        } else {
            arr[k] = arr2[j];
            j++;
            k++;
        }
    }

    while (i < n1) {
        arr[k] = arr1[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = arr2[j];
        j++;
        k++;
    }
}

void mergeSort(int l, int r) {
    while (l < r) {
        int mid = (l + r - 1) / 2;
        mergeSort(l, mid);
        mergeSort(mid + 1, r);
        merge(l, mid, r);
    }
}

void printArray(int arr[], int length) {
    for (int i = 0; i < length; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    printArray(arr, n);
    mergeSort(0, n - 1);
    printArray(arr, n);
}

I am not getting what is wrong with the code, when tried to debug it, it was calling mergeSort function, again and again with the same value.

Answer 1

There are many bugs hiding in plain sight in your merge function:

• int n1 = mid - l + l; has an l where there should be a 1. Naming a variable l is risky as depending on the font, l looks confusingly close to 1.
• arr1[i] = arr[l + 1]; should be arr1[i] = arr[l + i];
• for (int i = 0; i < n1; i++) should be for (int i = 0; i < n2; i++) for the second loop.
• arr1[i] = arr[mid + i]; should be arr2[i] = arr[mid + i];

Also note that it would be more consistent with C++ idioms to use the index of the element past the end of the slice instead of the index to the last element of the slice as many algorithmic books advise. This also allows for unsigned index types, such as size_t and remove the need for tricky +1 / -1 adjustments.

Here is a modified version:

#include <iostream>

using namespace std;

void merge(size_t lo, size_t mid, size_t hi) {
    size_t n1 = mid - lo;
    size_t n2 = hi - mid;
    int arr1[n1], arr2[n2];

    for (size_t i = 0; i < n1; i++) {
        arr1[i] = arr[lo + i];
    }

    for (size_t i = 0; i < n2; i++) {
        arr2[i] = arr[mid + i];
    }

    int i = 0, j = 0, k = lo;

    while (i < n1 && j < n2) {
        if (arr1[i] <= arr2[j]) {
            arr[k++] = arr1[i++];
        } else {
            arr[k++] = arr2[j++];
        }
    }

    while (i < n1) {
        arr[k++] = arr1[i++];
    }

    while (j < n2) {
        arr[k++] = arr2[j++];
    }
}

void mergeSort(size_t lo, size_t hi) {
    while (hi - lo > 1) {
        size_t mid = lo + (hi - lo) / 2;
        mergeSort(lo, mid);
        mergeSort(mid, hi);
        merge(lo, mid, hi);
    }
}

void printArray(const int arr[], size_t length) {
    for (size_t i = 0; i < length; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = { 6, 1, 9, 6, 4, 7, 3 };
    size_t n = sizeof(arr) / sizeof(*arr);

    printArray(arr, n);
    mergeSort(0, n);
    printArray(arr, n);
    return 0;
}

merge does not actually need to save the elements of the right half as they are never overwritten before they are read. Here is a simplified version:

void merge(size_t lo, size_t mid, size_t hi) {
    size_t n1 = mid - lo;
    size_t n2 = hi - mid;
    int arr1[n1];

    for (size_t i = 0; i < n1; i++) {
        arr1[i] = arr[lo + i];
    }

    int i = 0, j = mid, k = lo;

    while (i < n1) {
        if (j >= hi || arr1[i] <= arr[j]) {
            arr[k++] = arr1[i++];
        } else {
            arr[k++] = arr[j++];
        }
    }
}