Merge Sort - return a new array instead of copying merged array to input array

Question

I'm trying to implement a very naive version of Merge Sort (not considering all the optimizations for this purpose) where my goal is to return a new copy of the merged array rather than the traditional way of passing the input array by reference and copying the merged elements into it.

To that end, my code is as below:

vector<int> merge(vector<int> left, vector<int> right)
{
    vector<int> result;
    int leftIdx = 0;
    int rightIdx = 0;
    int resultIdx = 0;

    while (leftIdx < left.size() && rightIdx < right.size()) {
        if (left[leftIdx] < right[rightIdx]) {
            result[resultIdx++] = left[leftIdx++];
        } else {
            result[resultIdx++] = right[rightIdx++];
        }
    }

    while (leftIdx < left.size()) {
        result[resultIdx++] = left[leftIdx++];
    }

    while (rightIdx < right.size()) {
        result[resultIdx++] = right[rightIdx++];
    }

    return result;
}

vector<int> MergeSort(vector<int> intArr)
{
    vector<int> recresult;

    // base - if array is of length 1, nothing to do, return it as is
    if (intArr.size() == 1) {
        return intArr;
    } else {
        int mid = intArr.size() / 2;
        // copy left half
        vector<int> leftArr(intArr.begin(), intArr.begin() + mid);
        // copy right half
        vector<int> rightArr(intArr.begin() + mid, intArr.end());

        MergeSort(leftArr);
        MergeSort(rightArr);

        recresult = merge(leftArr, rightArr);
    }

    return recresult;
}

1. I know that this array from merge is a local array and hence I'm returning it to mergesort which will in turn return it to main. Am I wrong in assuming that this is not getting passed into and out from subsequent recursive calls?

2. My test input to this code is {1,0,9}. I should be getting {0,1,9} but I get 32767.

What am I missing here?

Answer 1

First for merge - you should pass const references to arguments, otherwise you make too many unnecessary copies. Also you get out of bound access to result as you create in empty and accessing by index. And it is not a good idea to use int for index. So simplified version could be:

vector<int> merge(const vector<int> &left, const vector<int> &right)
{
    vector<int> result;
    auto lit = left.begin();
    auto rit = right.begin();
    while( lit != left.end() || rit != right.end() ) {
        bool lft = false;
        if( rit == right.end() )
            lft = true;
        else {
            if( lit != left.end() )
                lft = *lit < *rit;
        }
        result.push_back( lft ? *lit++ : *rit++ );
   }
   return result;
}

or version that closer to your:

vector<int> merge(const vector<int> &left, const vector<int> &right)
{
    vector<int> result( left.size() + right.size() );
    auto rst = result.begin();
    auto lit = left.begin();
    auto rit = right.begin();
    while( lit != left.end() && rit != right.end() )
        *rst++ = *lit < *rit ? *lit++ : *rit++;

    std::copy( lit, left.end(), rst );
    std::copy( rit, right.end(), rst );
    return result;
}