I have tried to implement mergesort and am unable to find the exact problem of my code. The program shows no errors but I do not get a desired output

Question

Tried implementing mergesort, below is code. Let me know if anything is wrong. Is there any any error in my merge function? unable to point to the exact problem in my code. Any help regarding the same would be highly appreciated.

#include <iostream>
using namespace std;

Merge function to merge the two sorted arrays

void merge(int arr[], int start, int mid, int end) {
    int n1 = mid - start + 1;
    int n2 = end - mid;
    
    int arr1[n1], arr2[n2];
    for (int i = 0; i < n1; i++) {
        arr1[i] = arr[start + i];
    }
    for (int j = 0; j < n2; j++) {
        arr2[j] = arr[mid + 1 + j];
    }

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

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

Calling mergesort recursively

void merge_sort(int arr[], int start, int end) {
    if (start >= end) {
      return;
    }
    if (start < end) {
        int mid = start + (end - 1) / 2;
        merge_sort(arr, start, mid);
        merge_sort(arr, mid + 1, end);
        merge(arr, start, mid, end);
    }
}

Print function to print the array

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

Main function

int main() {
    int arr[] = { 6, 5, 12, 10, 9, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    
    merge_sort(arr, 0, n - 1);
    cout << "The sorted array is: " << endl;
    printArray(arr, n);
}

Answer 1

There are 2 bugs is the code:

• computing the mid point as int mid = start + (end - 1) / 2; is incorrect. You should instead write:

    int mid = start + (end - start) / 2;
  

• in the last loop in merge you increment i instead of j. Note that this loop is redundant as the remaining elements of arr2 are already at the end of arr.

You follow the classic convention in mergesort implementations where end is the index of the last element in the slice. This convention requires multiple +1 / -1 adjustments, it easy to get it wrong.

In C and related languages where array indices start at 0, it is more idiomatic to use a different convention: passing start as the index of the first element of the slice and end as the index just past the last element. This allows to specify empty splices and produces cleaner code.

Here is a modified version:

#include <iostream>

using namespace std;

// Merge function to merge the two sorted arrays
void merge(int arr[], int start, int mid, int end) {
    int n1 = mid - start;
    int n2 = end - mid;
    int arr1[n1], arr2[n2];

    for (int i = 0; i < n1; i++) {
        arr1[i] = arr[start + i];
    }
    for (int j = 0; j < n2; j++) {
        arr2[j] = arr[mid + j];
    }

    int i = 0;
    int j = 0;
    int p = start;
    
    while (i < n1 && j < n2) {
        if (arr1[i] <= arr2[j]) {
            arr[p] = arr1[i];
            i++;
        } else {
            arr[p] = arr2[j];
            j++;
        }
        p++;
    }
    while (i < n1) {
        arr[p] = arr1[i];
        i++;
        p++;
    }
    // the remaining elements from `arr2` are already in place in `arr`
}

// Calling mergesort recursively
void merge_sort(int arr[], int start, int end) {
    if (end - start > 1) {
        int mid = start + (end - start) / 2;
        merge_sort(arr, start, mid);
        merge_sort(arr, mid, end);
        merge(arr, start, mid, end);
    }
}

// Print function to print the array
void printArray(const int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

// Main function
int main() {
    int arr[] = { 6, 5, 12, 10, 9, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    
    merge_sort(arr, 0, n);
    cout << "The sorted array is: " << endl;
    printArray(arr, n);
    return 0;
}