CODEWITHSUNDEEP
c++algorithmsortingvectormergesort
Ujjwal.Maurya0619
Ujjwal.Maurya0619

Reputation: 25

Merge sort same output C++

I wrote the below code for merge sort but it's not working, And I am unable to find out problem! Every time the output becomes same as input, I think that problem may occur due to vector reference. I think mergeSort is not creating a new vector for sub array. But I am still confused.

input vector: 5, 4, 3, 2, 1
output: 5, 4, 3, 2, 1
Req output: 1, 2, 3, 4, 5

#include <iostream>
#include <vector>

using namespace std;

void merge(vector<int> &la, vector<int> &ra, vector<int> &A) {

    int i = 0, j = 0, k = 0;

    //  overwriting A using its solved sub arrays i.e la, ra
    while (i < la.size() && j < ra.size()) {
        if (la[i] <= ra[j]) {
            A[k] = la[i];
            i++;
            k++;
        } else {
            A[k] = ra[j];
            j++;
            k++;
        }
    }

    //  if any subarray left then
    while (i < la.size()) {
        A[k] = la[i];
        k++;
        i++;
    }
    while (j < ra.size()) {
        A[k] = ra[j];
        k++;
        j++;    
    }
}

mergeSort function:

void mergeSort(vector<int> &A) {

    if (A.size() < 2)
        return;

    int len = A.size();
    vector<int> la, ra;

    for (int i = 0; i < len / 2; i++)
        la.push_back(A[i]);

    for (int i = len / 2; i < len; i++)
        ra.push_back(A[i]);

    //  dividing the proble into subproblem
    mergeSort(la);
    mergeSort(ra);

    //  merging the solved subproblem
    merge(la, ra, A);
}

Driver function:

int main(void) {
    int arr[] = { 5, 4, 3, 2, 1 };
    vector<int> A(arr, arr + 5);
    for (int i = 0; i < A.size(); i++)
        cout << A[i] << " ";
    cout << endl;

    mergeSort(A);

    for (int i = 0; i < A.size(); i++)
        cout << A[i] << " ";
    return 0;
}

Upvotes: 0

Views: 83

Answers (1)

chqrlie
chqrlie

Reputation: 144695

The code posted does not seem to have a problem.

Executing it produces the expected output: 1 2 3 4 5, so there is something else going on that could cause your observations: you might be running an executable produced by a previous or at least different version of the code.

Upvotes: 1

Related Questions