CODEWITHSUNDEEP
c++mergesort
eb80
eb80

Reputation: 4738

Understanding Part of Recursive Implementation of MergeSort C++

I am struggling to get my mind around the following recursive implementation of mergesort in C++

What gets me is that since the vector is being passed by reference and vec.clear() is being called, how does that not wipe out the vector even after some of the merging has been done. For example, when the base is hit, the function returns the top frame on the stack and proceeds bak down the stack. However, the function needs to merge more than once and before each merge the vector is being cleared, which I would think means the space in memory (since it is pass by reference) is cleared out and we lose what was already merged? I can understand how this method would work if it was passed by value, but this is passed by reference so I am confused.

void merge(vector<int> &final, vector<int> &left, vector<int> &right) {
    while (left.size() > 0 || right.size() > 0) {
        if (right.size() == 0) {
            final.push_back(left.at(0));
            left.erase(remove(left.begin(), left.end(), left.at(0)), left.end());
        }
        else if (left.size() == 0) {
            final.push_back(right.at(0));
            right.erase(remove(right.begin(), right.end(), right.at(0)), right.end());
        } else if (left.at(0) <= right.at(0)) {
            final.push_back(left.at(0));
            left.erase(remove(left.begin(), left.end(), left.at(0)), left.end());
        } else if (right.at(0) < left.at(0)) {
            final.push_back(right.at(0));
            right.erase(remove(right.begin(), right.end(), right.at(0)), right.end());
        }
    }
}

void sort(vector<int> &vec) {
    int n = vec.size();

    // BASE CASE
    if (n <= 1) {
        return;
    }

    // GENERAL CASE / RECURSIVE CASE
    vector<int> leftVec;
    vector<int> rightVec;

    for (int i = 0; i < n; i++) {
        if (i < n / 2) {
            leftVec.push_back(vec.at(i));
        } else {
            rightVec.push_back(vec.at(i));
        }
    }

    sort(leftVec);
    sort(rightVec);
    vec.clear();
    merge(vec, leftVec, rightVec);
}

Upvotes: 0

Views: 245

Answers (1)

Mark Ransom
Mark Ransom

Reputation: 308111

The contents of vec have been copied to leftVec and rightVec before the clear call, so no information has been lost. You haven't given the source for merge but we can assume it copies the contents back into vec.

Upvotes: 2

Related Questions