#include <iostream>
#include <vector>

using namespace std;

template <typename RandomIt>
void MergeSort(RandomIt range_begin, RandomIt range_end) {
    auto vec = vector<typename iterator_traits<RandomIt>::value_type>(range_begin, range_end);

    if (vec.size() < 2) {
        return;
    }

    MergeSort(vec.begin(), vec.begin() + vec.size() / 2);
    MergeSort(vec.begin() + vec.size() / 2, vec.end());

    auto first_half(vec.begin());
    auto second_half(vec.begin() + vec.size() / 2);

    while (first_half != vec.begin() + vec.size() / 2 && second_half != vec.end()) {
        if (*first_half < *second_half) {
            *range_begin = *first_half;
            ++first_half;
        } else {
            *range_begin = *second_half;
            ++second_half;
        }
        ++range_begin;
    }

    while (first_half != vec.begin() + vec.size() / 2) {
        *range_begin = *first_half;
        ++first_half;
        ++range_begin;
    }

    while (second_half != vec.end()) {
        *range_begin = *second_half;
        ++second_half;
        ++range_begin;
    }
}

int main() {
  vector<int> v = {6, 4, 7, 6, 4, 4, 0, 1};
  MergeSort(begin(v), end(v));
  for (int x : v) {
    cout << x << " ";
  }
  cout << endl;
  return 0;
}