#include <iostream>
#include <vector>
#include <algorithm>

void merge(std::vector<int>::iterator& beg, std::vector<int>::iterator& mid, std::vector<int>::iterator& end) {
  std::vector<int> a(end-beg);
  std::vector<int>::iterator i = beg;
  std::vector<int>::iterator j = mid;
  for (int it = 0; it < end-beg; ++it) {
    if ((*i <= *j && i != mid)|| j == end) {
      a[it]= *i;
      ++i;
    } else if ((*i > *j && j != end) || i == mid) {
      a[it]= *j;
      ++j;
    }
  }
  for (int k = 0; k < end-beg; ++k) {
        *(beg + k) = a[k];
  }
}

void mergeSort(std::vector<int>::iterator beg, std::vector<int>::iterator end) {
  if (end - beg <= 1) {
    return;
  }
  std::vector<int>::iterator mid = beg + (end - beg)/2;
  mergesort(beg, mid);
  mergesort(mid, end);
  merge(beg, mid, end);
}