What's wrong with my C++ Merge Sort code?

Question

I used This for reference, but after getting wrong output, I matched every single line in the code, but I can't find whats wrong. My code-

#include <iostream>

using namespace std;

void printA(int a[] , int l , int r){
    cout << endl;
    for(int i = l ; i < r ; i++)
        cout<< a[i] <<" ";
    cout<< endl;
}
void merge(int arr[] , int l , int m , int r){
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[n1];
    int R[n2];
    for(int i=0 ; i < n1 ; i++)
        L[i]=arr[l+i];
    for(int j=0 ; j < n2 ; j++)
        R[j] = arr[m+1+j];
    int i=0, j=0, k=0;
    while(i < n1 && j < n2){
        if(L[i] <= R[j]){
            arr[k] = L[i];
            i++;
        }
        else{
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while(i < n1){
        arr[k] = L[i];
        i++;
        k++;
    }
    while(j < n2){
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[] , int l , int r){
    if(l < r){
        int m = l + (r-l)/2;

        //cout<<"l="<<l<<" m="<<m<<" r="<<r<<" Array";
        //printA(arr,l,r+1);

        mergeSort(arr, l, m);
        mergeSort(arr , m+1 ,r);
        merge(arr, l, m, r);
    }
}

 int main(){
     int n;
     cin >> n;
     int arr[n];
     for(int i=0 ; i < n ; i++)
        cin>> arr[i];
    cout<< "Before: ";
    printA(arr, 0 ,n);
     mergeSort(arr, 0 , n-1);
     cout<<"After";
     printA(arr, 0 ,n);
     return 0;
 }

Input: 5

5 4 3 2 1

Output: Before:

5 4 3 2 1

After

1 2 2 1 5

I cant figure out what's wrong, please help.

Ignore these- sa asfasfadgdsg sdg sgdkdjgjngjknrgjk ns

Sure, I cleaned it up

S4rt-H4K
– S4rt-H4K

2018-05-05 11:56:47 +00:00
Commented May 5, 2018 at 11:56 — S4rt-H4K
– S4rt-H4K, Commented May 5, 2018 at 11:56

kiloalphaindia · Accepted Answer · 2018-05-05 11:47:22Z

1

When you think of 'r' pointing to the first element after the range, then you can fix your program easily:

#include <iostream>

using namespace std;

void printA(int a[],int l,int r){
    cout<<endl;
    for(int i=l;i<r;i++)
        cout<<a[i]<<" ";
    cout<<endl;
}
void merge(int arr[],int l,int m,int r){
    int n1 = m-l; // was: int n1 = m-l+1;
    int n2 = r-m;
    int L[n1];
    int R[n2];
    for(int i=0;i<n1;i++)
        L[i]=arr[l+i];

    for(int j=0;j<n2;j++)
        R[j] = arr[m+j]; // was: R[j] = arr[m+1+j];


    int i=0,j=0,k=l; // was: int i=0,j=0,k=0;
    while(i < n1 && j < n2){
        if(L[i]<=R[j]){
            arr[k] = L[i];
            i++;
        }
        else{
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while(i<n1){
        arr[k] = L[i];
        i++;
        k++;
    }
    while(j<n2){
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[],int l,int r){
    if(r - l > 1){ // was: if(l<r){
        int m = l+(r-l)/2;
        //cout<<"l="<<l<<" m="<<m<<" r="<<r<<" Array";
        //printA(arr,l,r+1);
        mergeSort(arr,l,m);
        mergeSort(arr,m,r); // was: mergeSort(arr,m+1,r);
        merge(arr,l,m,r);
    }
}

int main(){
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
        cin>>arr[i];
    cout<<"Before: ";
    printA(arr,0,n);
    mergeSort(arr,0,n); // was: mergeSort(arr,0,n-1);
    cout<<"After";
    printA(arr,0,n);
    return 0;
}

answered May 5, 2018 at 11:47

kiloalphaindia

5613 silver badges8 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

S4rt-H4K Over a year ago

Thanks a lot! But why do we keep k = 1? Aren't we supposed to modify the original array from the start, i.e., k = 0?

S4rt-H4K Over a year ago

Ohh, so k = l and not 1. Thats where I am messing up.

Collectives™ on Stack Overflow

What's wrong with my C++ Merge Sort code?

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related