What's the issue in this merge sort algorithm in c++

Question

I have learnt this from gfg course even the link they have given for the code is similar code I have written but still not able to find the problem in this:

#include <iostream>
#include <algorithm>

using namespace std;

void merge(int a[], int low, int mid, int high) {
    int m = mid - low + 1, n = high - mid;
    int left[m], right[n];
    for (int i = 0; i < m; i++) {
        left[i] = a[low + i];
    }
    for (int j = 0; j < n; j++) {
        right[j] = a[m + j];
    }
    int i = 0, j = 0, k = low;
    while (i < m && j < n) {
        if (left[i] <= right[j]) {
            a[k] = left[i];
            i++;
            k++;
        } else {
            a[k] = right[j];
            j++;
            k++;
        }
    }
    while (i < m) {
        a[k] = left[i];
        i++;
        k++;
    }
    while (j < n) {
        a[k] = right[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r) {
    if (l >= r) {
        return;
    }
    if (r > l) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

int main() {
    int n;
    cout << "enter size of array: ";
    cin >> n;
    int arr[n];
    cout << "enter element in array: ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    mergeSort(arr, 0, n - 1);
    cout << "array after sort: \n";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

Here is the code on giving input as {10,5,30,15,7} it returns output as {5,10,10,15,30}

Here is the output screen shot for reference

Your program is not a valid C++ program, as C++ doesn't have [variable-length arrays](https://en.wikipedia.org/wiki/Variable-length_array). Use [`std::vector`](https://en.cppreference.com/w/cpp/container/vector) instead. And please get [some good books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) to learn C++ properly. — Some programmer dude, Jan 30 '21 at 05:34
@Someprogrammerdude I have good books I think you didn't read the title properly if just search merge sort in C++ you will get this type of solutions only not the vector one. I wanted to know the reason of this code not working not ignoring and Implemet in other way around but thanks anyway — pratham choudhary, Jan 30 '21 at 05:54
Just because many inexperienced programmers use something doesn't mean it's good, or even right. Your argument is similar to the whole "if everybody jumped off a cliff I would too" argument. Read your books, learn good habits, and learn to recognize bad things (most everything coming out of so-called "competition" sites these days) and most importantly not just copy blindly but also think for your self. — Some programmer dude, Jan 30 '21 at 06:14
As for the issue with your code, debugging debugging debugging. Knowing how to debug your code and how to use a debugger is almost (if not more) important than knowing the language. It's a crucial skill for all programmers. — Some programmer dude, Jan 30 '21 at 06:17
I now man debugging is important but these platforms are made to clarify problems especially for beginners like me if you don't want to help please don't discourage thank you. — pratham choudhary, Jan 30 '21 at 06:40

selbie · Accepted Answer · 2021-01-30T06:18:20.423

1

You are confusing your m variable (size of left array) with mid (last index in left array)

Instead of this:

for(int j=0;j<n;j++){
    right[j] = a[m+j];
}

This:

for (int j = 0; j < n; j++) {
    right[j] = a[mid + j + 1];
}

Pro-tip: One letter variables are fine as an index in a for-loop. But for anything else give the name an obvious meaning. For example, instead of m and n, name them leftArraySize and rightArraySize. Instead of l and r, name them firstIndex and lastIndex. It will be a lot obvious where the bugs are when you use obtuse variable names where the names have meaning.

edited Jan 30 '21 at 06:18

answered Jan 30 '21 at 05:57

selbie

100,020
15
103
173

thank you so much changing variable names accordingly worked and yes I got confused that's why it was not noticeable . Thankyou I will remember for future. – pratham choudhary Jan 30 '21 at 06:16

chqrlie · Answer 2 · 2021-01-30T11:57:54.077

The bug in the code is in the initialization loop for right: a[m + j] should be a[mid + j + 1]

Note however that copying the right half of the array is unnecessary as these elements are copied before they eventually get overwritten.

The merge function can be simplified as:

void merge(int a[], int low, int mid, int high) {
    int m = mid - low + 1;
    int left[m];
    for (int i = 0; i < m; i++) {
        left[i] = a[low + i];
    }
    int i = 0, j = mid + 1, k = low;
    while (i < m && j <= high) {
        if (left[i] <= a[j]) {
            a[k] = left[i];
            i++;
            k++;
        } else {
            a[k] = a[j];
            j++;
            k++;
        }
    }
    while (i < m) {
        a[k] = left[i];
        i++;
        k++;
    }
}

Note also that all these +1 / -1 adjustments are confusing and error prone. You can simplify the code by passing high as the index of the element beyond the slice to sort and mid the index of the first element of the right half. Naming a variable l can be error prone too, as l looks confusingly similar to 1.

Here is a modified version of the code:

#include <iostream>
#include <algorithm>

using namespace std;

void merge(int a[], int low, int mid, int high) {
    int m = mid - low;
    int left[m];
    for (int i = 0; i < m; i++) {
        left[i] = a[low + i];
    }
    int i = 0, j = mid, k = low;
    while (i < m && j < high) {
        if (left[i] <= a[j]) {
            a[k++] = left[i++];
        } else {
            a[k++] = a[j++];
        }
    }
    while (i < m) {
        a[k++] = left[i++];
    }
}

void mergeSort(int arr[], int low, int high) {
    if (high - low >= 2) {
        int mid = low + (high - low) / 2;
        mergeSort(arr, low, mid);
        mergeSort(arr, mid, high);
        merge(arr, low, mid, high);
    }
}

int main() {
    int n;
    cout << "enter size of array: ";
    cin >> n;
    int arr[n];
    cout << "enter element in array: ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    mergeSort(arr, 0, n);
    cout << "array after sort: \n";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
    return 0;
}

The merge function can be further simplified as:

void merge(int a[], int low, int mid, int high) {
    int m = mid - low;
    int left[m];
    for (int i = 0; i < m; i++) {
        left[i] = a[low + i];
    }
    int i = 0, j = mid, k = low;
    while (i < m) {
        if (j >= high || left[i] <= a[j]) {
            a[k++] = left[i++];
        } else {
            a[k++] = a[j++];
        }
    }
}

What's the issue in this merge sort algorithm in c++

2 Answers2