Your big mistake is not using iterators.

As a result you pass your vectors by value, which causes the vectors to be copied a lot.

std::vector<int> MergeSort(std::vector<int> arr)
                                            ^^^    A copy of the array is made when you call this function.


std::vector<int> Merge(std::vector<int> arr1, std::vector<int> arr2)
                                        ^^^^ Copy              ^^^^ Copy

Now, you could mitigate this by passing the values by reference. But I think a better solution is to pass iterators into the container. That way you also allow for other container types.

Luckily for you, a return is a move, not a copy - so that is not as big a problem as a copy.

template<typename I>
void MergeSort(I begin, I end)

template<typename I,
void Merge(I src1Begin, I src1End, I src2Begin, I src2End, I dstBegin);

Your big mistake is not using iterators.

As a result you pass your vectors by value, which causes the vectors to be copied a lot.

std::vector<int> MergeSort(std::vector<int> arr)
                                            ^^^    A copy of the array is made when you call this function.


std::vector<int> Merge(std::vector<int> arr1, std::vector<int> arr2)
                                        ^^^^ Copy              ^^^^ Copy

Now, you could mitigate this by passing the values by reference. But I think a better solution is to pass iterators into the container. That way you also allow for other container types.

Luckily for you, a return is a move, not a copy - so that is not as big a problem as a copy.

template<typename I>
void MergeSort(I begin, I end)

template<typename I,
void Merge(I src1Begin, I src1End, I src2Begin, I src2End, I dstBegin);

You're big mistake is not using iterators.

As a result you pass you vectors by VALUE which causes the vectors to be copied a lot.

std::vector<int> MergeSort(std::vector<int> arr)
                                            ^^^    A copy of the array is made when you call this function.


std::vector<int> Merge(std::vector<int> arr1, std::vector<int> arr2)
                                        ^^^^ Copy              ^^^^ Copy

Now you could mitigate this by passing the values by reference. But I think a better solution is to pass iterators into the container (that way you also allow for other container types). Luckily for you a return is a move not a copy (so that is not as big a problem as a copy).

template<typename I>
void MergeSort(I begin, I end)

template<typename I,
void Merge(I src1Begin, I src1End, I src2Begin, I src2End, I dstBegin);

Your big mistake is not using iterators.

As a result you pass your vectors by value, which causes the vectors to be copied a lot.

std::vector<int> MergeSort(std::vector<int> arr)
                                            ^^^    A copy of the array is made when you call this function.


std::vector<int> Merge(std::vector<int> arr1, std::vector<int> arr2)
                                        ^^^^ Copy              ^^^^ Copy

Now, you could mitigate this by passing the values by reference. But I think a better solution is to pass iterators into the container. That way you also allow for other container types. 

Luckily for you, a return is a move, not a copy - so that is not as big a problem as a copy.

template<typename I>
void MergeSort(I begin, I end)

template<typename I,
void Merge(I src1Begin, I src1End, I src2Begin, I src2End, I dstBegin);