std::out_of_range: vector exception in Mergesort algorithm

Question

I am trying to implement the Mergesort algorithm in C++. You can see my implementation below. When I run the algorithm I get the following error: libc++abi.dylib: terminating with uncaught exception of type std::out_of_range: vector Abort trap: 6

While this is my first time working in C++, I assume that this error means that I pass in an index that is outside the bounds of some vector. Is this correct?

If this is correct, I cannot figure out where I am exceeding the bounds of some vector. However, I printed a few values to the console and noticed that the program fails to print the elements in the vector right. Maybe this gives a hint for where the index is out of bounds.

Mergesort implementation

#include <iostream>
#include <vector>

void merge(std::vector<int> left, std::vector<int> right, std::vector<int> array)
{
    int lengthLeft = left.size();
    int lengthRight = right.size();

    int i = 0; // index of smallest unpicked element in left
    int j = 0; // index of smallest unpicked element in right
    int k = 0; // position to be filled in array
    while (i < lengthLeft && j < lengthRight)
    {
        if (left.at(i) <= right.at(j))
        {
            array.at(k) = left.at(i);
            k++;
            i++;
        }
        else
        {
            array.at(k) = right.at(j);
            k++;
            j++;
        }
    }
    while (i < lengthLeft)
    {
        array.at(k) = left.at(i);
        k++;
        i++;
    }
    while (j < lengthRight)
    {
        array.at(k) = right.at(j);
        k++;
        j++;
    }
}

std::vector<int> mergesort(std::vector<int> array)
{
    int length = array.size();
    std::cout << "Array Size: " << length << '\n';

    if (length < 2)
    {
        return array;
    }

    int mid = length / 2;
    std::cout << "mid = " << mid << '\n';

    // Temporary vectors.
    std::vector<int> left(mid);
    std::vector<int> right(length - mid);
    std::cout << "Left size: " << left.size() << '\n';
    std::cout << "Right size: " << right.size() << '\n';

    // Moving elements into temporary vectors.
    for (int i = 0; i <= mid; i++)
    {
        left.at(i) = array.at(i);
        std::cout << "Left at i: " << left.at(i) << '\n';
    }
    for (int i = mid + 1; i < length; i++)
    {
        right.at(i) = array.at(i);
        std::cout << "Right at i: " << right.at(i) << '\n'; // <-- THIS DOES NOT PRINT
    }

    mergesort(left);
    mergesort(right);
    merge(left, right, array);

    return array;
}

int main()
{
    std::vector<int> vect = {5, 4, 3, 2, 1};

    for (int i : vect)
    {
        std::cout << i << " " << '\n';
    }

    mergesort(vect);

    for (int i : vect)
    {
        std::cout << i << '\n';
    }

    return 0;
}

Console output

5
4
3
2
1
Array Size: 5
mid = 2
Left size: 2
Right size: 3
Left at i: 5
Left at i: 4
libc++abi.dylib: terminating with uncaught exception of type std::out_of_range: vector
Abort trap: 6

Answer 1

There are a few things wrong with your code, but the error is being given by this loops

for (int i = 0; i <= mid; i++)
{
    left.at(i) = array.at(i);
    std::cout << "Left at i: " << left.at(i) << '\n';
}
for (int i = mid + 1; i < length; i++)
{
    right.at(i) = array.at(i);
    std::cout << "Right at i: " << right.at(i) << '\n'; // <-- THIS DOES NOT PRINT
}

To fix your error you have to change the first for to for (int i = 0; i < mid; i++) replacing the <= with just <, so it gets the first two digits.
On the second you should change to for (int i = 0; i < length - mid; i++) also change right.at(i) = array.at(i); to right.at(i) = array.at(mid + i);, this will make sure you get the remaining 3, the problem here was that you were starting in mid which was 2 and the right vector only has size of 3, since vector are indexed at 0 you were starting on the last index and the next iteration was out of the bounds of it.

So the hole section would be like this

for (int i = 0; i < mid; i++)
{
    left.at(i) = array.at(i);
    std::cout << "Left at i: " << left.at(i) << '\n';
}
for (int i = 0; i < length - mid; i++)
{
    right.at(i) = array.at(mid + i);
    std::cout << "Right at i: " << right.at(i) << '\n'; // <-- THIS DOES NOT PRINT
}

That being said your program wouldn't still sort the vector, C++ passes arguments by value, that means that every time you call a function with a certain input it will create a new variable with the same data.
Your mergesort function is supposed to receive a vector and change the values on it, here you have two options, or change the function to return a new vector or you pass the vector to this function by reference, using &, this instead of creating a new vector inside the function with the same values, will send the memory reference of the variable to the function, that way the function has access to the same variable.
Your function should be changed to

void merge(std::vector<int> &left, std::vector<int> &right, std::vector<int> &array)
{ ... }

std::vector<int> mergesort(std::vector<int> &array)
{ ... }

Some times will be useful to pass by reference other not, you will get that in time, but usually performance-wise it's a good practice because you are not creating new variables with each function.

If it wasn't clear or you want a better explanation just ask.

Tip

Careful naming your variables, you shouldn't use reserved names, array is a name reserved by C++, you should have another name instead.

It's not actually a reserved word, only conflicts if the programmer uses using namespace std, as stated by @user4581301

Reserved is a loaded term. In C++ Reserved means you can't use this, no matter what. array is not reserved. Using array as an identifier will only cause problems if is included and the std namespace has been short-circuited with using namespace std (something the wise programmer avoids).