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.