MergeSort3

#include "test_runner.h"
#include <algorithm>
#include <memory>
#include <vector>
#include <typeinfo>
#include <cstdint>
#include <list>
#include "iostream"
#include <utility>

using namespace std;

void print(string message,vector<int> &numbers){
    cout << message << endl;
    for(auto &it:numbers){
        cout << it << ",";
    }
    cout << endl;
}

// ::working code::
template <typename RandomIt>
void MergeSort(RandomIt range_begin, RandomIt range_end) {
    if(range_end - range_begin <3){
        return;
    }
    vector<typename RandomIt::value_type> elements(move(range_begin),move(range_end));
    vector<typename RandomIt::value_type> space,space2,space3,res;
    move(elements.begin(),elements.begin()+(elements.end() - elements.begin())/3,back_inserter(space));
    move(elements.begin()+(elements.end() - elements.begin())/3,elements.begin()+(elements.end() - elements.begin())/3*2,back_inserter(space2));
    MergeSort(space.begin(),space.end());
    MergeSort(space2.begin(),space2.end());
    MergeSort(elements.begin()+(elements.end() - elements.begin())/3*2,elements.end());
    merge(make_move_iterator(space.begin()),make_move_iterator(space.end()),make_move_iterator(space2.begin()),make_move_iterator(space2.end()),back_inserter(res));
    merge(make_move_iterator(res.begin()),make_move_iterator(res.end()),make_move_iterator(elements.begin()+(elements.end() - elements.begin())/3*2),make_move_iterator(elements.end()),back_inserter(space3));
    move(make_move_iterator(space3.begin()),make_move_iterator(space3.end()),range_begin);
//      for(size_t i=0;i<space3.size();i++,++range_begin){
//      *range_begin = move(space3[i]);
//  }
}


void TestIntVector() {
  vector<int> numbers = {6, 1, 3, 9, 1, 9, 8, 12, 1};
  MergeSort(begin(numbers), end(numbers));
  ASSERT(is_sorted(begin(numbers), end(numbers)));
}



int main() {
  TestRunner tr;
  RUN_TEST(tr, TestIntVector);
  return 0;
}