Weird bug in mergesort

Question

I've just programmed the following simple merge function in mergesort which follows exactly the one written in CLRS book.

#include<iostream>
#include<vector>
#include<limits>

using namespace std;

//Define the numerical positive infinity
const int INFP = numeric_limits<int>::max();

void MERGE(vector<int> A, int p, int q, int r){
    //Create the size of left and right array
    int n1 = q-p+1;
    int n2 = r-q;
    //Create the left array
    vector<int> L(n1+1);
    for(int i=0; i<n1;i++){
        L[i] = A[i];
    }
    L[n1] = INFP; //Insert sentinel here!
    //Create the right array
    vector<int> R(n2+1);
    for(int i=0; i<n2;i++){
        R[i] = A[q+i+1];
    }
    L[n2] = INFP; //Insert sentinel here!
    int i = 0;
    int j = 0;
    for(int k = 0; k <= r; k++){
        if(L[i]<=R[j]){
            A[k] = L[i];
            i=i+1;
        }
        else{
            A[k] = R[j];
            j=j+1;
        }
    }
    for(int m=0;m<4;m++){
        cout<< A[m] << " ";
    }
    cout << endl;
}

int main(){
    //test for merge function:
    vector<int> A(4);
    A[0]=1;
    A[1]=3;
    A[2]=2;
    A[3]=4;
    MERGE(A,0,1,3);
    for(int m=0;m<4;m++){
        cout<< A[m] << " ";
    }
    cout << endl;
    return 0;
}

However, it gave me the following print out, which really confused me:

1 2 3 4
1 3 2 4

I don't know if it's the problem of the void function that I can't use void function for vectors or something else.

Really hope someone can help me out. Thanks!

Note: I can tell you one "bug" already. You're passing your vector in by value. Even if your code worked the *caller* would not see the fruits of your labors. And you can make your algorithm significantly easier with [`std::merge`](http://en.cppreference.com/w/cpp/container/list/merge) and/or [`std::inplace_merge`](http://en.cppreference.com/w/cpp/algorithm/inplace_merge). In fact, it becomes down-right-trivial. — WhozCraig, Sep 15 '13 at 15:20

score 3 · Answer 1 · answered Sep 15 '13 at 15:20

3

It's because you pass the vector by value, meaning you modify a local copy. Pass it by reference instead.

answered Sep 15 '13 at 15:20

Some programmer dude

400,186
35
402
621

Could you please give me an example how to pass it by reference? Thanks! – Cancan Sep 15 '13 at 15:21
1

@Cancan No, that should be very clearly explained by any beginners book or tutorial about the C++ language. If you don't have any, [here is a good list](http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). – Some programmer dude Sep 15 '13 at 15:22
Ok, just realized I was too lazy, but I've already figured it out. Thanks! – Cancan Sep 15 '13 at 15:24

Weird bug in mergesort

1 Answers1