#include <cmath>
#include <map>
#include <string>
#include <algorithm>
#include <iostream>
#include <set>
#include <utility>
#include <vector>
#include <numeric>
#include <chrono>
#include <type_traits>
#include <cassert>
#include <sstream>
#include <unordered_map>
#include <stdexcept>
#include <stack>
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 It>
//auto GetPermutations(It range_begin, It range_end){
//    sort(range_begin, range_end);
//    reverse(range_begin, range_end);
//    vector<string> ans;
//    do{
//        ans.push_back(PrintRange(range_begin, range_end));
//    } while(prev_permutation(range_begin, range_end));
//
//    return ans;
//}
//template <typename RandomIt>
//void MergeSort(RandomIt range_begin, RandomIt range_end){
//    typename iterator_traits<RandomIt>::difference_type i = distance(range_begin, range_end) / 2;
//    cout << " d " << n << endl;
//    vector<RandomIt> tmp;
//    for(n = 0; n < *i; ++n){
//        //typename iterator_traits<RandomIt>::value_type tmp = *range_begin;
//        tmp[n] = range_begin;
//        //cout << tmp[n] << endl;
//        /**range_begin++ = *--range_end;
//        *range_end = tmp;*/
//    }
//}
//template<class BidirIt>
//void MergeSort(BidirIt first, BidirIt last){
//    typename std::iterator_traits<BidirIt>::difference_type n = std::distance(first, last);
//    for(--n; n > 0; n -= 2){
//        typename std::iterator_traits<BidirIt>::value_type tmp = *first;
//
//        *first++ = *--last;
//        *last = tmp;
//    }
//}
//template <typename It>
//void MergeSort(It first, It last){
   /* vector<int> v1(last - first);
    vector<int>::iterator Iter1;
    if(*first < *last){
        typename iterator_traits<It>::difference_type center = (last - first) / 2;
        MergeSort(*first, center);
        MergeSort(++center, *last);
        merge(*first, center, center, *last, v1.begin());
    }*/


    /*for(Iter1 = v1.begin(); Iter1 != v1.end(); Iter1++)
        cout << *Iter1 << " "s;*/

    //vector<int> left;
    //vector<int> right;
   // vector<int> v1(last - first);
   // vector<int>::iterator middle(first + (last - first) / 2);
   // vector<int>::iterator Iter;
    /*for(auto it = first; it != last; ++it){
        if(distance(it, middle) > 0){
            left.push_back(*it);
        } else{
            right.push_back(*it);
        }
    }*/
    /*for(Iter = v1.begin(); Iter != v1.end(); Iter++)
        cout << *Iter << " "s;
    cout << endl;*/
//}
//template <typename It>
//void MergeSort(It first, It last){
//    vector<It> left;
//    vector<It> right;
//    for(It it = first; it != last; ++it){
//        if(distance(it, first + (last - first) / 2) > 0){
//            left.push_back(it);
//        } else{
//            right.push_back(it);
//        }
//    }
//    merge(left.begin(), left.end(), right.begin(), right.end(), first,
//        [](int elem1, int elem2){
//            if(elem1 > 0)
//                elem1 = -elem1;
//            if(elem2 > 0)
//                elem2 = -elem2;
//            return elem1 < elem2;
//        }
//    );
//}
template <typename It>
void MergeSort(It first, It last){
    vector<typename iterator_traits<It>::value_type> a(first, last);
    //vector<int> a(first, last);
    //typename iterator_traits<It>::value_type tmp = *first;
    typename iterator_traits<It>::difference_type size = (a.end() - a.begin()) / 2;

    MergeSort(a.begin(), a.begin() + size);
    MergeSort(a.begin() + size, a.end());
    merge(a.begin(), a.begin() + size, a.begin() + size, a.end(), first/*,
        [](int elem1, int elem2){
            if(elem1 > 0)
                elem1 = -elem1;
            if(elem2 > 0)
                elem2 = -elem2;
            return elem1 < elem2;
        }
    */);
}

int main(){
    vector<int> test_vector(10);

    iota(test_vector.begin(), test_vector.end(), 1);
    //random_shuffle(test_vector.begin(), test_vector.end());
    PrintRange(test_vector.begin(), test_vector.end());
    MergeSort(test_vector.begin(), test_vector.end());
    PrintRange(test_vector.begin(), test_vector.end());
    /*auto result = GetPermutations(test_vector.begin(), test_vector.end());
    for(const auto &s : result){
        cout << s;
    }*/
    return 0;
}