Implementing merge sort algorithm issue

Question

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;
}

I recommend you start using a debugger since the cerr does not allow you to single step execution and look at variables. — Thomas Matthews
– Thomas Matthews, Commented Jan 7, 2014 at 1:40

Ben Jackson · Accepted Answer · 2014-01-06 21:34:21Z

1

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.

answered Jan 6, 2014 at 21:34

Ben Jackson

94.7k9 gold badges103 silver badges154 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

eigenharsha · Accepted Answer · 2018-01-24 06:45:51Z

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());
    }
}

Collectives™ on Stack Overflow

Implementing merge sort algorithm issue

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related