template <typename InputIteratorFirst, typename InputIteratorSecond,
typename OutputIterator, typename Comparator>
OutputIterator Merge(InputIteratorFirst begin_first_iter, InputIteratorFirst end_first_iter,
               InputIteratorSecond begin_second_iter, InputIteratorSecond end_second_iter,
               OutputIterator buffer_iter, Comparator comparator) {
    while (begin_first_iter != end_first_iter && begin_second_iter != end_second_iter) {
        if (comparator(*begin_first_iter, *begin_second_iter)) {
            *buffer_iter++ = *begin_first_iter++;
        } else {
            *buffer_iter++ = *begin_second_iter++;
        }
    }
    buffer_iter = std::move(begin_first_iter, end_first_iter, buffer_iter);
    return std::move(begin_second_iter, end_second_iter, buffer_iter);
}


template <typename Iterator, typename Comparator>
void MergeSort(Iterator begin, Iterator end, Iterator begin_buffer_iter, Comparator comparator) {
    auto distance = std::distance(begin, end);
    if (distance < 2) {
        return;
    }
    auto middle = begin + distance / 2;
    MergeSort(begin, middle, begin_buffer_iter, comparator);
    MergeSort(middle, end, begin_buffer_iter, comparator);
    auto end_buffer_iter = Merge(begin, middle, middle, end, begin_buffer_iter, comparator);
    std::move(begin_buffer_iter, end_buffer_iter, begin);
}


template <typename Iterator, typename Comparator>
void MergeSort(Iterator begin, Iterator end, Comparator comparator) {
    using ValueType = typename std::iterator_traits<Iterator>::value_type;
    std::vector<ValueType> buffer;
    buffer.reserve(std::distance(begin, end));
    MergeSort(begin, end, buffer.begin(), comparator);
}