CODEWITHSUNDEEP
c++
user2980956
user2980956

Reputation: 11

Implementing merge sort algorithm issue

I am implementing a merge sort algorithm and I am receiving an std::bad_alloc in the merge algorithm and using the cerr statement I have found that my error is in first loop of the merge algorithm. However I am unable to figure out what is wrong.

vector<int> VectorOps::mergeSort(vector<int> toSort)
{
    if(toSort.size() <= 1)
    {
        return toSort;

    }
    vector<int> left;
    vector<int> right;

    int half = toSort.size()/2;
    for(int i = 0; i < half; ++i)
    {
        left.push_back(toSort.at(i));
    }

    for(int i = half; i < toSort.size(); ++i)
    {
        right.push_back(toSort.at(i));
    }

    //merge algorithim

    vector<int> toReturn;
    while(left.size() > 0 || right.size() > 0)
    {
        cerr << "The numbers are "<< endl;
        if(left.size() > 0 && right.size() > 0)
        {
            if(left.at(0) <= right.at(0))
            {
                toReturn.push_back(left.at(0));
            }
            else
            {
                toReturn.push_back(right.at(0));
            }
        }
        else if(left.size() > 0)
        {
            toReturn.push_back(left.at(0));
        }
        else if(right.size() > 0)
        {
            toReturn.push_back(right.at(0));
        }
    }

    return toReturn;
}

Upvotes: 1

Views: 101

Answers (2)

eigenharsha
eigenharsha

Reputation: 2231

As @BenJackson already mentioned in answer...

The size of left and right never change. You just get the element from the vector and not removed from it. So, the size of toReturn grows without bound.

vector hasn't any method to remove head element but you can achieve like 

left.erase(left.begin());

For your solution either you remove a head element from vector or only iterate vector and get value.

vector<int> toReturn;
int l = 0; r = 0;
while (l < left.size() || r < right.size()) {

    if (l < left.size() && r < right.size()) {
        if (left.at(l) <= right.at(r)) {
            toReturn.push_back(left.at(l++));
        } else {
            toReturn.push_back(right.at(r++));
        }
    } else if (l < left.size()) {
        toReturn.push_back(left.at(l++));
    } else if (r < right.size()) {
        toReturn.push_back(right.at(r++));
    }
}

Merge implementation through erasing head element.

while (left.size() > 0 || right.size() > 0) {
    cerr << "The numbers are " << endl;
    if (left.size() > 0 && right.size() > 0) {
        if (left.at(0) <= right.at(0)) {
            toReturn.push_back(left.at(0));

            //erase head element from left
            left.erase(left.begin());

        } else {
            toReturn.push_back(right.at(0));

            //erase head element from right
            right.erase(right.begin());

        }
    } else if (left.size() > 0) {
        toReturn.push_back(left.at(0));

        //erase head element from left
        left.erase(left.begin());
    } else if (right.size() > 0) {
        toReturn.push_back(right.at(0));

        //erase head element from right
        right.erase(right.begin());
    }
}

Upvotes: 0

Ben Jackson
Ben Jackson

Reputation: 93890

In:

while(left.size() > 0 || right.size() > 0)

The size of left and right never change (you don't remove the head element) so toReturn grows without bound and you run out of memory.

Upvotes: 1

Related Questions