Why am I getting a stack overflow error from this merge sort? (C++)

Question

I'm trying to use a merge sort to sort a list of IP address that have been converted to unsigned longs. The vector contains 18647 numbers if that makes a difference or not. I've done a merge sort using C# before but this is the first time I've tried it in C++ so I don't know if there's something simple I'm missing. Here's the code I have at the moment:

vector<unsigned long> Sorter::mergeSort( vector<unsigned long> v){
    if( v.size() <= 1 ){
        return v;
    }
    vector<unsigned long> left, right;
    int mid = v.size() / 2;
    for( int i = 0; i < mid; i++ ){
        left.push_back( v[i] );
    }
    for( unsigned int j = mid; j <= v.size(); j++ ){
        right.push_back( v[j] );
    }
    left = Sorter::mergeSort( left );
    right = Sorter::mergeSort( right );
    return Sorter::merge( left, right );
}

vector<unsigned long> Sorter::merge( vector<unsigned long> left, vector<unsigned long> right){
    vector<unsigned long> result;
    while( left.size() > 0 || right.size() > 0 ){
        if( left.size() > 0 && right.size() > 0 ){
            if( left[0] <= right[0] ){
                result.push_back( left[0] );
                left.erase( left.begin() );
            }else{
                result.push_back( right[0] );
                right.erase( right.begin() );
            }
        }else if( left.size() > 0 ){
            result.push_back( left[0] );
            left.erase( left.begin() );
        }else if( right.size() > 0 ){
            result.push_back( right[0] );
            right.erase( right.begin() );
        }
    }
    return result;
}

Community · Accepted Answer · 2017-05-23 12:28:21Z

2

for( unsigned int j = mid; j <= v.size(); j++ )
                             ^^

You should use j < v.size() or j <= v.size() -1 (array index starts from 0), otherwise, you have index out of bound error.

Meanwhile, it is better to pass the vector by reference to save some cost.

Another point, since you used vector, it is OK to have 18647 numbers since memory space of the vector header is allocated on Stack but elements of vector are allocated on free store. See this thread for more information:

When vectors are allocated, do they use memory on the heap or the stack?

edited May 23, 2017 at 12:28

CommunityBot

11 silver badge

answered Mar 15, 2013 at 3:36

taocp

23.7k10 gold badges52 silver badges62 bronze badges

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

Collectives™ on Stack Overflow

Why am I getting a stack overflow error from this merge sort? (C++)

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related