Confusing Behaviors in Sorting with C++ vector

Question

I just begin to program in C++ and I meet some confusing results when implementing a mergeSort algorithm with std::vector. I used to program in Python and Java. It is the first time I use C++. Besides, I search for some information about reference and pointer. But it does not solve my problem.

void merge(vector<int>& arr, int low, int mid, int high){
    vector<int> tmp;
    int left = low;
    int right = mid + 1;
    while (left <= mid && right <= high)
    {
        if (arr[left] < arr[right])
        {
            tmp.push_back(arr[left]);
            left ++;
        } else
        {
            tmp.push_back(arr[right]);
            right ++;
        }
    }
    while (left <= mid)
    {
        tmp.push_back(arr[left]);
        left ++;   
    }
    while (right <= high)
    {
        tmp.push_back(arr[right]);
        right ++;
    }
    for (int i = low; i <= high; i++)
    {
        arr[i] = tmp[i];
    }
}

void mergeSort(vector<int> arr, int start, int tail){
    if (start >= tail)
    {
        return;
    }
    int mid = start + (tail - start)/2;
    mergeSort(arr, start, mid);
    mergeSort(arr, mid + 1, tail);
    merge(arr, start, mid, tail);
    // Here, I want to see the process
    print_vec(arr);
    cout<<"==================="<<endl;
}

int main(){
    vector<int> arr{6,7,1,3,5,7,4};
    mergeSort(arr, 0, arr.size() - 1);
    print_vec(arr);
    return 0;
}

And the output is:

6 7 1 3 5 7 4 
===================
6 7 655696 0 5 7 4 
===================
1 3 6 7 5 7 4 
===================
6 7 1 3 5 7 4 
===================
6 7 1 3 0 -1 -1112271603 
===================
5 6 7 4 7 1 3 
===================
6 7 1 3 5 7 4 

I do not understand why the program generates some weird numbers such as "655696, -1112271603, -1".

I have tested the "merge" function. It seems correct.

It is really exotic to debug this. I even do not know how to search for this problem on Google. So I ask it here.

Answer 1

There are two major issues in your code:

First, your mergeSort takes its vector argument by value, which means that any action it performs on that vector will be lost when the function returns. To fix this, pass that argument by reference:

void mergeSort(vector<int>& arr, int start, int tail) // Pass "arr" by reference
{
    //...

Second, the last for loop of your merge function is attempting to use the same indexes for both its given array (arr) and its local array (tmp); this is not correct, and will result in attempting to access out-of-bounds elements of tmp, causing undefined behaviour (the weird values you see).

The index used for the tmp array should start at zero. So, to fix the issue, add a second loop variable (let's call it j) to the loop, initialize that to zero, and increment it as with the i index at the end of each loop:

void merge(vector<int>& arr, int low, int mid, int high)
{
    //
    // Other code as is ...
    //
    for (int i = low, j = 0; i <= high; i++, j++) {
        arr[i] = tmp[j]; // The "tmp" elements will ALWAYS start from ZERO
    }
}

One other note: for indexes of STL containers (like std::vector), and return values of member functions like .size(), you really should be using the size_t type rather than int. Your compiler will no doubt warn you about this, if you let it: clang gives me lots of the following:

warning : implicit conversion changes signedness: 'int' to 'std::vector::size_type' (aka 'unsigned long long') [-Wsign-conversion]