I'm new to recursion and trying to write merge sort code but it is not working properly

Question

I'm new to recursion and trying to write merge sort code but it is not working properly. I can't find my mistake. I have tried to dry run the code but failing in that and doesn't know the exact mistake.

#include<bits/stdc++.h>
using namespace std;

void merge(vector<int> &v,int lo,int mid,int hi){
    vector<int> temp;
    int i=lo;
    int j=mid;
    while(i<=mid-1 && j<=hi){
        if(v[i]<=v[j]){
            temp.push_back(v[i++]);
        }
        else{
            temp.push_back(v[j++]);
        }
    }
    while(i<=mid-1){
        temp.push_back(v[i++]);
    }
    while(j<=hi){
        temp.push_back(v[i++]);
    }
    for(int m=lo;m<=hi;i++){
        v[m]=temp[m-lo];
    }
}
void mergeSort(vector<int> &v,int lo,int hi){
    if(lo<hi){
        int mid=lo+(hi-lo)/2;
        mergeSort(v,lo,mid);
        mergeSort(v,mid+1,hi);
        merge(v,lo,mid+1,hi);
    }
}
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector<int> v(n);
        for(int i=0;i<n;i++){
            cin>>v[i];
        }
        mergeSort(v,0,n-1);
        for(int i=0;i<n;i++){
            cout<<v[i]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

A typo in the last `while loop` of `merge` function. Replace `i` by `j`. — Damien, Mar 05 '22 at 11:36
See [Why should I not #include ?](https://stackoverflow.com/q/31816095) and [Why using namespace std is bad practice](https://stackoverflow.com/questions/1452721). — prapin, Mar 05 '22 at 12:46

score 1 · Answer 1 · answered Mar 05 '22 at 13:28

You have a typo in your last while loop. You're iterator on j, but incrementing on i. Your compiler should warning you that neither of the two mutable expressions in the loop condition (j, and hi) are being modified. I.e. turn up your warnings.

That said, that loop is pointless anyway You do not need to move already-sorted leftover high-partition data to temp, just to move it again back to the original vector. It's already where it belongs. The only leftover elements you're interested in are those left in the lower partition when the high partition finished first. Therefore your entire routine comes down to this:

void merge(std::vector<int> &v, int lo, int mid, int hi)
{
    std::vector<int> temp;
    int i = lo;
    int j = mid;
    while (i < mid && j <= hi)
    {
        if (v[i] <= v[j])
        {
            temp.push_back(v[i++]);
        }
        else
        {
            temp.push_back(v[j++]);
        }
    }
    while (i < mid)
    {
        temp.push_back(v[i++]);
    }

    for (size_t i=0; i<temp.size(); ++i)
        v[i+lo] = temp[i];
}

That should do it.

I'm new to recursion and trying to write merge sort code but it is not working properly

1 Answers1