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

score 2 · Answer 1 · edited May 23 '17 at 12:28

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?

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

1 Answers1