#include <iostream>
#include <vector>
using namespace std;

template <typename It>
void PrintRange(It range_begin, It range_end) {
    for (auto it = range_begin; it != range_end; ++it) {
        cout << *it << " "s;
    }
    cout << endl;
}

template <typename RandomIt, typename Type>
void MergeSort(RandomIt range_begin, RandomIt range_end) {
    int range_num = distance(range_begin, range_end); // количество элементов в контейнере
    if (range_num < 2) return;
    vector<Type> temp(range_num);
    copy(range_begin, range_end, temp.begin());

    auto mid = temp.begin() + (temp.end() - temp.begin()) / 2; // середина контейнера
    auto mid_copy = mid;
    MergeSort(temp.begin(), mid);
    MergeSort(mid+1, temp.end());
    merge(temp.begin(), mid, mid_copy, temp.end(), range_begin);
}