Recursive merge sort in C++ Any suggestions on how to improve this code (other than arbitrary call-stack depth)?

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

template &lt;typename T&gt;
void merge(const std::vector&lt;T&gt;&amp; left, const std::vector&lt;T&gt;&amp; right, std::vector&lt;T&gt;&amp; merged)
{
    auto i = left.begin();
    auto j = right.begin();
    auto k = merged.begin();

    while (i != left.end() &amp;&amp; j != right.end())
    {
        *k = (*i &lt; *j) ? *i : *j;
        if (*i &lt; *j) ++i;
        else ++j;
        ++k;
    }
    while (j != right.end())
    {
        *k = *j; ++k; ++j;
    }
    while (i != left.end())
    {
        *k = *i; ++k; ++i;
    }
}

template &lt;typename T&gt;
void merge_sort(std::vector&lt;T&gt;&amp; A)
{
    if (A.size() &lt;= 1) return;
    size_t mid = A.size() / 2;
    std::vector&lt;T&gt; left(A.begin(), A.begin() + mid);
    std::vector&lt;T&gt; right(A.begin() + mid, A.end());
    merge_sort(left);
    merge_sort(right);
    merge(left,right, A);
}

int main()
{
    std::vector&lt;int&gt; input = {19, 14, 17, 16, 12, 9, 15, 1, 2, 11, 7, 3, 10, 14};
    std::vector&lt;int&gt; sorted = {1, 2, 3, 7, 9, 10, 11, 12, 14, 14, 15, 16, 17, 19};
    bool success = true;
    merge_sort(input);
    for (size_t i = 0; i &lt; input.size(); ++i) if ( input[i] != sorted[i] ) success = false;
    std::cout &lt;&lt; "Merge sort " &lt;&lt; (success ? "passed\n" : "failed\n");
}
There is more efficient and idiomatic ways of implementing merge sort, yet I will assume your style. I have embedded my comments directly in your code whenever I have something to say:

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

template &lt;typename T&gt;
void merge(const std::vector&lt;T&gt;&amp; left_vector,
           const std::vector&lt;T&gt;&amp; right_vector,
           std::vector&lt;T&gt;&amp; merged_vector)
{
    /*
    auto i = left.begin();
    auto j = right.begin();
    auto k = merged.begin();
    */
    // Better names + names for end iterators in order not to call end() on each
    // iteration:
    auto left      = left_vector.begin();
    auto right     = right_vector.begin();
    auto merged    = merged_vector.begin();
    auto left_end  = left_vector.end();
    auto right_end = right_vector.end();

    /*
    while (i != left.end() &amp;&amp; j != right.end())
    {
        *k = (*i &lt; *j) ? *i : *j;
        if (*i &lt; *j) ++i;
        else ++j;
        ++k;
    }*/
    // Would be more efficient since you compare only once per iteration:
    while (left != left_end &amp;&amp; right != right_end)
    {
        if (*right &lt; *left)
        {
            *merged = *right;
            ++right;
        }
        else
        {
            *merged = *left;
            ++left;
        }

        ++merged;
    }

    /*
    while (j != right.end())
    {
        *k = *j; ++k; ++j;
    }
    while (i != left.end())
    {
        *k = *i; ++k; ++i;
    }*/
    // Here you could use std::copy. Only one of these two calls will have an
    // effect, since either left &lt; left_end or right &lt; right_end:
    std::copy(left, left_end, merged);
    std::copy(right, right_end, merged);
}

template &lt;typename T&gt;
void merge_sort(std::vector&lt;T&gt;&amp; A)
{
    if (A.size() &lt;= 1) return;
    size_t mid = A.size() / 2;
    std::vector&lt;T&gt; left(A.begin(), A.begin() + mid);
    std::vector&lt;T&gt; right(A.begin() + mid, A.end());
    merge_sort(left);
    merge_sort(right);
    merge(left,right, A);
}

int main()
{
    std::vector&lt;int&gt; input = {19, 14, 17, 16, 12, 9, 15, 1, 2, 11, 7, 3, 10, 14};
    std::vector&lt;int&gt; sorted = {1, 2, 3, 7, 9, 10, 11, 12, 14, 14, 15, 16, 17, 19};
    /*
    merge_sort(input);
    bool success = true;
    merge_sort(input);
    for (size_t i = 0; i &lt; input.size(); ++i) if ( input[i] != sorted[i] ) success = false;
    std::cout &lt;&lt; "Merge sort " &lt;&lt; (success ? "passed\n" : "failed\n");
     */
    // You can write better:
    merge_sort(input);
    std::cout &lt;&lt; "Merge sort passed: "
              &lt;&lt; std::boolalpha
              &lt;&lt; std::equal(input.begin(),
                            input.end(),
                            sorted.begin(),
                            sorted.end())
              &lt;&lt; std::endl;
}


Hope that helps.