Recursive merge sort in C++

Question

Any suggestions on how to improve this code (other than arbitrary call-stack depth)?

#include <iostream>
#include <vector>

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

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

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

int main()
{
    std::vector<int> input = {19, 14, 17, 16, 12, 9, 15, 1, 2, 11, 7, 3, 10, 14};
    std::vector<int> 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 < input.size(); ++i) if ( input[i] != sorted[i] ) success = false;
    std::cout << "Merge sort " << (success ? "passed\n" : "failed\n");
}

Answer 1

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 <iostream>
#include <vector>
#include <algorithm>

template <typename T>
void merge(const std::vector<T>& left_vector,
           const std::vector<T>& right_vector,
           std::vector<T>& 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() && j != right.end())
    {
        *k = (*i < *j) ? *i : *j;
        if (*i < *j) ++i;
        else ++j;
        ++k;
    }*/
    // Would be more efficient since you compare only once per iteration:
    while (left != left_end && right != right_end)
    {
        if (*right < *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 < left_end or right < right_end:
    std::copy(left, left_end, merged);
    std::copy(right, right_end, merged);
}

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

int main()
{
    std::vector<int> input = {19, 14, 17, 16, 12, 9, 15, 1, 2, 11, 7, 3, 10, 14};
    std::vector<int> 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 < input.size(); ++i) if ( input[i] != sorted[i] ) success = false;
    std::cout << "Merge sort " << (success ? "passed\n" : "failed\n");
     */
    // You can write better:
    merge_sort(input);
    std::cout << "Merge sort passed: "
              << std::boolalpha
              << std::equal(input.begin(),
                            input.end(),
                            sorted.begin(),
                            sorted.end())
              << std::endl;
}

Hope that helps.