C++ Merge Sort Implementation
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&lt;int&gt; MergeSort(std::vector&lt;int&gt; arr)
                                            ^^^    A copy of the array is made when you call this function.


std::vector&lt;int&gt; Merge(std::vector&lt;int&gt; arr1, std::vector&lt;int&gt; 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&lt;typename I&gt;
void MergeSort(I begin, I end)

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