C++ Merge Sort Implementation Edit: A follow up question can be found here.



My first try at mergesort, without resorting to any references:

#include &lt;iostream&gt;
#include &lt;vector&gt;

std::vector&lt;int&gt; Merge(std::vector&lt;int&gt;, std::vector&lt;int&gt;);
std::vector&lt;int&gt; MergeSort(std::vector&lt;int&gt;);

int main()
{
    // No need to review this, it was just for testing purposes
    std::vector&lt;int&gt; a;
    for (int i = 0; i &lt; 100; i++) {
        a.push_back(6000.0 * rand() / RAND_MAX);
    }
    for (int i = 0; i &lt; a.size(); i++) {
        std::cout &lt;&lt; a[i] &lt;&lt; " ";
    }
    std::cout &lt;&lt; "\n";
    a = MergeSort(a);
    for (int i = 0; i &lt; a.size(); i++) {
        std::cout &lt;&lt; a[i] &lt;&lt; " ";
    }
    std::cout &lt;&lt; "\n";
    return 0;
}

std::vector&lt;int&gt; Merge(std::vector&lt;int&gt; arr1, std::vector&lt;int&gt; arr2) {
    int size1 = arr1.size();
    int size2 = arr2.size();
    std::vector&lt;int&gt; res(size1 + size2, 0);
    int i1 = 0;
    int i2 = 0;
    while (i1 &lt; size1 &amp;&amp; i2 &lt; size2) {
        if (arr1[i1] &lt; arr2[i2]) {
            res[i1 + i2] = arr1[i1];
            i1++;
        }
        else {
            res[i1 + i2] = arr2[i2];
            i2++;
        }
    }
    while (i1 &lt; size1) {
        res[i1 + i2] = arr1[i1];
        i1++;
    }
    while (i2 &lt; size2) {
        res[i1 + i2] = arr2[i2];
        i2++;
    }
    return res;
}

std::vector&lt;int&gt; MergeSort(std::vector&lt;int&gt; arr) {
    if (arr.size() &lt; 2) {
        return arr;
    }
    else if (arr.size() == 2) {
        // If array is of size 2, return it sorted
        if (arr[0] &gt; arr[1]) {
            arr[1] += arr[0];
            arr[0] = arr[1] - arr[0];
            arr[1] -= arr[0];
        }
        return arr;
    }
    else {
        // Recursively split in halves until all vectors are size 1 or 2, then merge
        return Merge(
            MergeSort(std::vector&lt;int&gt;(arr.begin(), arr.begin() + arr.size() / 2)),
            MergeSort(std::vector&lt;int&gt;(arr.begin() + arr.size() / 2, arr.end()))
        );
    }
}


A few questions:


Have I implemented a merge sort correctly? Or is it some other sort?
How can I make it work for multiple data types rather than just int?
I imagine it's not very efficient (I don't know much about std::vector&lt;T&gt;.begin or std::vector&lt;T&gt;.end), how could I make it more efficient?
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);