[NO-PARSE]template < template <typename, typename...> class C,
typename T,
typename... TParams >
C<T, TParams...> sorted_merge(C<T, TParams...> &lhs, C<T, TParams...> &rhs)
{
C<T, TParams...> merged;
auto lhs_it = lhs.begin(), rhs_it = rhs.begin();
while (lhs_it != lhs.end() && rhs_it != rhs.end())
{
merged.insert(merged.end(), *lhs_it < *rhs_it
? *lhs_it++ : *rhs_it++);
}
std::copy(lhs_it, lhs.end(), std::inserter(merged, merged.end()));
std::copy(rhs_it, rhs.end(), std::inserter(merged, merged.end()));
return merged;
}
template < template <typename, typename...> class C,
typename T,
typename... TParams >
C<T, TParams...> merge_sort(const C<T, TParams...> &c)
{
if (c.size() == 1) return c;
auto it_mid = c.begin();
std::advance(it_mid, c.size() / 2);
C<T, TParams...> lhs(c.begin(), it_mid);
C<T, TParams...> rhs(it_mid, c.end());
lhs = merge_sort(lhs);
rhs = merge_sort(rhs);
return sorted_merge(lhs, rhs);
}[/NO-PARSE]