Merge Sort using C++ Program not getting correct output

Question

I dont know whats wrong with this code but ive spend way too much time to figure out the problem but still couldnt, I think there is some error with the copying of array because every other thing seems to be correct

please check this code-

#include<iostream>
using namespace std;


void MergeArray(int arr[],int lb,int mid,int ub){
    int i=lb;
    int j=mid+1;
    int k=0;
    int newarr[ub-lb+1];

//condition required for comparison between the split parts
    while(i<=mid && j<=ub){
        if(arr[i] < arr[j]){
            newarr[k]=arr[i];
            k++;
            i++;
        }
//basically a[j]<a[i] in this else condition
        else{
            newarr[k]=arr[j];
            k++;
            j++;
        }
    }
//all th left out elements in a[i] when a[j] is finished are added to newarr
    while(i<=mid){
        newarr[k]=arr[i];
        k++;
        i++;
    }
//all th left out elements in a[j] when a[i] is finished are added to newarr
    while(j<=ub){
        newarr[k]=arr[j];
        k++;
        j++;
    }

//copying all the elements of newarr to original arr
//i think this part has something messed up
   for(int i=lb;i<=ub;i=i+1){
        arr[i]= newarr[i];
    }

}


void MergeElements(int arr[], int lb,int ub){
    int mid;
    if(lb<ub){
        mid=(lb+ub)/2;
        //spliting into 2 arts**
        MergeElements(arr,lb,mid);
        MergeElements(arr,mid+1,ub);
        //merging in sorted order**
        MergeArray(arr,lb,mid,ub);
    }

}

int main(){
    int n;
    cout<<"enter the size of the array"<<endl;
    cin>>n;
    int arr[n];
    cout<<"please enter the elements of the array"<<endl;
    for(int i=0;i<n;i++){
        cout<<"enter the element no."<<i<<endl;
        cin>>arr[i];
    }

    MergeElements(arr,0,n-1);

    cout<<"\tSorted Array Elements"<<endl;
    for(int i=0;i<n;i++){
        cout<<arr[i]<<"\t";
    }
return 0;
}

i think i am not able to get the array correctly because everything else seems to be correct according to me please check

Related: https://stackoverflow.com/q/24650626/2610810 – Caleth Feb 25 '20 at 13:46 — Caleth, Feb 25 '20 at 13:46

score 1 · Accepted Answer · answered Feb 25 '20 at 13:30

Well, I'm going to bypass the issue you have with using a variable-length array (VLA) in C++ (for now - VLAs are not allowed in Standard C++) and, first, post the solution to your problem. This is (as you have correctly 'guessed' in your comments) in this loop:

//i think this part has something messed up
   for(int i=lb;i<=ub;i=i+1){
        arr[i]= newarr[i];
    }

Here, although the i index (which starts at the given lower bound, lb) is correct for the arr array, it is not correct for the newarr array! This is created locally, with a size ub - lb + 1 (correct) but the indexes start at zero - so you need to remove the lb offset for newarr:

   for (i = lb; i <= ub; i++) { // NOTE: You've already declared "int i" - a new one will give a 'hides previous declaration' warning
        arr[i] = newarr[i - lb]; // *** You need to remove the lower-bound offset!
    }

On the issue of VLAs in C++: I believe GCC/g++ supports these but, if you want to comply with Standard C++, you should use a std::vector. So, in place of:

int newarr[ub - lb + 1];

use:

std::vector<int> newarr(size_t(ub - lb + 1));

and similarly use std::vector<int> arr(n); in your main function. For minimal changes to your code, you can still keep your void MergeElements(int arr[], int lb, int ub) signature but, to call it using the std::vector you need to give the address of the first element. So, in main use this:

MergeElements(&arr[0], 0, n - 1);

Feel free to ask for further clarification and/or explanation.

Thank you! now code is working fine , but i still dont understand the lb part, accoding to what i understood - the `lb` is 0 only for the array `arr` and there is some other value for array `newarr` so i need to subtract the value of `lb` fro the array `newarr` is this correct? — WuzerHaun, Feb 25 '20 at 13:43
@Sushant078 The `newarr` array/vector is a **sub-array** of the main one, and its first element starts at `0`! In the given `arr` argument, the first element (that you use) has `lb` as its index. So, when you copy back into that array, the element `arr[lb]` should be replaced with the *first* element of your sub-array, which is `newarr[0]`. Similarly, `arr[lb+1]` will be copied from `newarr[1]`, and so forth. The index for the latter is always that of the first with the `lb` offset subtracted. — Adrian Mole, Feb 25 '20 at 13:46
@Sushant078 Note the starting values of `j` and `k` - this is doing the same thing. — Adrian Mole, Feb 25 '20 at 13:49

Vlad from Moscow · Answer 2 · 2020-02-25T13:43:29.010

Write the loop that copies the array newarr into arr like

//copying all the elements of newarr to original arr
//i think this part has something messed up
   for(int i=lb, k = 0;i<=ub; i++, k++){
        arr[i]= newarr[k];
    }

Pay attention to that variable length arrays is not a standard C++ feature. Instead of the variable length array newarr you can use the standard container std::vector<int>. Also using standard algorithms makes the implementation of the functionMergeArray more simpler. Here you are

void MergeArray(int arr[],int lb,int mid,int ub){
    std::vector<int> newarr(ub-lb+1 );

    std::merge( arr + lb, arr + mid + 1, arr + mid + 1, arr + ub + 1, newarr.begin() );
    std::copy( newarr.begin(), newarr.end(), arr + lb );
}

score 0 · Answer 3 · answered Feb 25 '20 at 13:43

The loop below this comment

// copying all the elements of newarr to original arr

uses the same index for the source and destination – and it should not. The newarr[] content to be copied starts at index 0, whilst its destination area in arr[] starts from index lb.

Merge Sort using C++ Program not getting correct output

3 Answers3