Why does this merge sort algorithm not work properly?

Question

I get no errors or warnings. Here's my code:

#include <iostream>

void merge(int arr[], int l, int m, int r);
void mergeSort(int arr[], int l, int r);

int main(){
    int arr[11] = {1, 9, 2, 5, 3, 10, 4, 8, 6, 7};

    mergeSort(arr, 0, 10);

    for(int i = 0; i < 11; i++){
        std::cout << arr[i] << "\t";
    }
    return 0;
}

void merge(int arr[], int l, int m, int r){
    int i = l;      // starting point of left subarray
    int j = m + 1;  // starting point of right subarray
    int k = l;      // starting point of temporary array
    int temp[11];
    while(i <= m && j <= r){
        if(arr[i] <= arr[j]){
            temp[k] = arr[i];
            i++;
        } else {
            temp[k] = arr[j];
            j++;
        }
        k++;
    }
    while(i <= m){
        temp[k] = arr[i];
        k++; i++;
    }
    while(j <= r){
        temp[k] = arr[j];
        k++; j++;
    }
    for(int s = l; s < 11; s++){
        arr[s] = temp[s];
    }
}

void mergeSort(int arr[], int l, int r){
    if(l < r) {
        int m = (l + r) / 2; // middle
        mergeSort(arr, l, m); // left subarray
        mergeSort(arr, m + 1, r); // right subarray
        merge(arr, l, m, r);
    }
}

This is what I get when I compile and run:

0 1 2 3 4 9 4199851 7208472 7667712 7669136 1996860265

It seems like the left part is sorted - although there's no 0 in the original array, and then everything messes up and the right part is all nonsense.

If anyone can help me out I'd really appreciate it - thank you.

Answer 1

The problem is with the merge function. You have to loop through l to r, inclusive not 11. Please see the reference code for a better understanding.

Reference Code

#include <iostream>

void merge(int arr[], int l, int m, int r);
void mergeSort(int arr[], int l, int r);

int main(){
    int arr[11] = {1, 9, 2, 5, 3, 10, 4, 8, 6, 7};

    mergeSort(arr, 0, 10);

    for(int i = 0; i < 11; i++){
        std::cout << arr[i] << "\t";
    }
    return 0;
}

void merge(int arr[], int l, int m, int r){
    int i = l;      // starting point of left subarray
    int j = m + 1;  // starting point of right subarray
    int k = l;      // starting point of temporary array
    int temp[11];
    while(i <= m && j <= r){
        if(arr[i] <= arr[j]){
            temp[k] = arr[i];
            i++;
        } else {
            temp[k] = arr[j];
            j++;
        }
        k++;
    }
    while(i <= m){
        temp[k] = arr[i];
        k++; i++;
    }
    while(j <= r){
        temp[k] = arr[j];
        k++; j++;
    }
    for(int s = l; s <= r; s++){
        arr[s] = temp[s];
    }
}

void mergeSort(int arr[], int l, int r){
    if(l < r) {
        int m = (l + r) / 2; // middle
        mergeSort(arr, l, m); // left subarray
        mergeSort(arr, m + 1, r); // right subarray
        merge(arr, l, m, r);
    }
}

Output

0 1 2 3 4 5 6 7 8 9 10