What's wrong in this code(Merge Sort)

#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define int long long

vi result;

void length(int n) {
    result.resize(n);
}

void Merge(int arr[], int l, int mid, int r) {
    int i = l;
    int j = mid+1;
    int k = 0; // For result array
    while(i <= mid && j <=r) {
        if(arr[i] <= arr[j]) {
            result[k] = arr[i];
            i++;k++;
        }
        else {
            result[k] = arr[j];;
            j++;k++;
        }
    }
        while(i <= mid) {
            result[k] = arr[i];
            i++;k++;
        }
        while(j <= r) {
            result[k] = arr[j];;
            j++; k++;
        }
}

void MergeSort(int arr[], int l, int r) { // l-> first position of array, r-> last positon..
    if(r > l) {
        // 1. Find Mid value
        int mid = (l + r) / 2;
        // 2. Divide
        MergeSort(arr,l, mid);
        MergeSort(arr,mid+1, r);
        // Merge these elements
        Merge(arr, l, mid, r);
    }
}

int32_t main() {
    int n;
    cin>>n;
    int arr[n];
    for(int i=0 ;i<n;i++)
        cin>>arr[i];
    length(n);
    MergeSort(arr,0,n-1);
    for(auto x: result) {
        cout<<x<<" ";
    }
    cout<<"\n";
    return 0;
}
1 Like

Please put your code between pair of three back ticks (```). Also, mention what’s going wrong.

Hi!

Please copy your code in places like pastebin like this.

Alternatively you can use hide details feature like

This
#include <whatever>
int main() {
     cout << "See how much neater and readable this code is!\n";
     return 0;
}

It helps to separate your code from your question, and improve readability and will be easier to debug.

Also make sure to include as many details as possible.

As for your question, in the Mergesort algorithm you recursively divide the array into two, sort them and then merge them.

While you have merged the two arrays in the vector result, the array (l, r) does not become sorted after you call Mergesort(l, r)

To fix this, once, you have obtained result, copy it back to the original array,

Add this line to your code inside the Merge function, at the end

Fix
for (int i=l;i<=r;++i) {
    arr[i] = result[i-l];
}

It should then work!
Edit : @suman_18733097 was right, I overlooked the indexing, however the mistake I hope was clear.

1 Like

I guess I found the error. In the function Merge(), after merging the two segments into vector result, you are supposed to copy the entire vector again into the original array.
So, the following snippet should to be added at the end. ( I am sorry I am not aware of vectors, so I am using array for result)

for(int i=0,j=l;j<=r;i++,j++)
{
    arr[j] = result[i];
}
1 Like

I guess your fix doesn’t work. You are iterating the segment result[l,r], while we are supposed to iterate the segment result[0,r-l].