PHP Templated Container MergeSort Implementation

[AceInfinity]

So I wanted to use my own merge sort implementation, but allow it to be available for multiple container types within the STL that are templated, and to keep this generic functionality I also needed my own function(s) to be templates. Container differences include having more than 1 template type, so I also needed to allow this. Additionally, not all containers have push_back(), like std::map<T, U> for instance, but a std::vector<T> does... I came up with a pretty convoluted solution, but I think it works perfect!

[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]

std::back_inserter uses push_back internally, so I had to swap over to std::iterator instead. Additionally, std::map<T, U> iterators didn't like me adding a numeric type to the iterator to advance it, so I used std::advance() instead from <iterator> to do this and avoid a loop that would advance the iterator by the number of times I needed.

You can test this implementation with the following (C++11) code:

[NO-PARSE]int main()
{
  std::vector<int> v { 1, 5, 3, 2, 7, 4, 6 , 9, 8 };
  std::vector<int> v_sorted = merge_sort(v);
  for (const auto &it : v_sorted)
    std::cout << it << ' ';

  std::endl(std::cout);
  
  std::map<char, int> m
  {
    { 'A', 1 },
    { 'C', 4 },
    { 'B', 2 }
  };
  std::map<char, int> m_sorted = merge_sort(m);
  for (const auto &it : m_sorted)
    std::cout << it.first << " -> " << it.second << '\n';
}[/NO-PARSE]

Don't forget to include the proper headers:

[NO-PARSE]#include <iostream>
#include <map>
#include <vector>
#include <iterator>
#include <algorithm>[/NO-PARSE]

Enjoy! :thumbsup2:

 

[AceInfinity]

NOTE: std::map is automatically sorted by key! I'm just using this as a demonstration to show you that it will still work with different template types and param counts. You could still get this to sort a similar container that does not automatically sort by creating the appropriate overloads.