sorted_range_merger.cpp

template<typename Iterator>
struct merger
{
    using Value = typename std::iterator_traits<Iterator>::value_type;
    using SortedRange = std::pair<Iterator, Iterator>;

    SortedRange operator()(SortedRange const &lhs, SortedRange const &rhs) const {
        assert(lhs.second == rhs.first);
        std::vector<Value> tmp(lhs.first, lhs.second); //Copy the left range
        std::merge(
                std::begin(tmp), std::end(tmp), // Left container copy (source)
                rhs.first, rhs.second,          // Right container (source)
                lhs.first);                     // Left container (destination)
        return SortedRange(lhs.first, rhs.second);
    }
};