C++ Merge Sort returning original vector

Question

I have been attempting to make a merge sort using vectors in C++ and am running into an issue where any vector input is sorted into its original order. I have based the algorithm off the geeks4geeks site here: https://www.geeksforgeeks.org/merge-sort/

So far I have spent about five hours attempting to find the source of the error and it seems that upon ending the merge function the vector somehow goes back to its original format, but I am unsure why. Any suggestions would be much appreciated.

#include <iostream>
#include <vector>

using namespace std;


void merge(vector<int> vect, int p, int q, int r) {

    int i, j, k, n1, n2;

    n1 = q - p + 1;
    n2 = r - q;

    vector<int> L, R;

    L.resize(n1);
    R.resize(n2);

    for (i = 0; i < n1; i++) {
        L[i] = vect[p + i];
    }

    for (j = 0; j < n2; j++) {
        R[j] = vect[q + 1 + j];
    }

    i = 0;
    j = 0;
    k = p;


    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            vect[k] = L[i];
            i++;

        }
        else {
            vect[k] = R[j];
            j++;
        }
        k++;
    }


    while (i < n1) {
        vect[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        vect[k] = R[j];
        j++;
        k++;
    }

}



void mergeSort(vector<int> vect, int p, int r) {
    if (p < r) {
        int q = (p + r) / 2;

        mergeSort(vect, p, q);
        mergeSort(vect, q + 1, r);

        merge(vect, p, q, r);


    }
}

int main() {

    vector<int> vect{4,3,5,6,7,8};
    mergeSort(vect, 0, vect.size() - 1);


    for (int i = 0; i < vect.size(); i++) { 
        cout << vect[i] << endl;
    }
}

Answer 1

First of all you should know the difference between:

• pass by value

• pass by reference

  Go and check it here.

---

Secondly, you should change your code as it is shown:

#include <iostream>
#include <vector>

//using namespace std; forget about it, start using std::whatever_it_is_in_here


void merge(std::vector<int> &vect, int p, int q, int r) // note the & near vect
{
    int i, j, k, n1, n2;

    n1 = q - p + 1;
    n2 = r - q;

    std::vector<int> L, R;

    L.resize(n1);
    R.resize(n2);

    for (i = 0; i < n1; i++) {
        L[i] = vect[p + i];
    }

    for (j = 0; j < n2; j++) {
        R[j] = vect[q + 1 + j];
    }

    i = 0;
    j = 0;
    k = p;


    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            vect[k] = L[i];
            i++;

        }
        else {
            vect[k] = R[j];
            j++;
        }
        k++;
    }


    while (i < n1) {
        vect[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        vect[k] = R[j];
        j++;
        k++;
    }

}



void mergeSort(std::vector<int> &vect, int p, int r) // note the & near vect
{
    if (p < r) {
        int q = (p + r) / 2;

        mergeSort(vect, p, q);
        mergeSort(vect, q + 1, r);

        merge(vect, p, q, r);


    }
}

int main()
{
    std::vector<int> vect{4,3,5,6,7,8};
    mergeSort(vect, 0, vect.size() - 1);


    for (int i = 0; i < vect.size(); i++)
        std::cout << vect[i] << "\n"; // note \n instead of std::endl

    return 0; // you forgot the return statement 
}

---

1. You forgot the return statement in the main function.
2. Stop using using namespace std. Check why here
3. Note the "\n" instead of std::endl. You can understand more of it here