// Remember to compile with -pthread

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

using std::cout;
using std::endl;
using std::vector;
using std::random_shuffle;
using std::swap;
using std::is_sorted;
using namespace std::chrono;

const int ARR_SIZE = 20000;

void bubble_down(vector<int>::iterator cur, const vector<int>::iterator &lo) {
  while (cur > lo && *cur < *(cur - 1)) {
    swap(*cur, *(cur - 1));
    cur--;
  }
}

void merge(const vector<int>::iterator &lo, const vector<int>::iterator &hi) {
  auto cur = (hi - lo) / 2 + lo;
  while (cur < hi) {
    bubble_down(cur, lo);
    cur++;
  }
}

void sort(const vector<int>::iterator &lo, const vector<int>::iterator &hi) {
  if (hi - lo <= 1) {
    return;
  }

  auto mid = (hi - lo) / 2 + lo;
  sort(lo, mid);
  sort(mid, hi);
  merge(lo, hi);
}

int main(int argc, char** argv) {
  vector<int> vec(ARR_SIZE);

  int i = 0;
  for (int& n : vec) {
    n = i++;
  }

  cout << "Shuffling..." << endl;
  random_shuffle(vec.begin(), vec.end());
  cout << (is_sorted(vec.begin(), vec.end()) ? "" : "not ") << "sorted " << endl;

  cout << "Sorting..." << endl;

  steady_clock::time_point start = steady_clock::now();
  sort(vec.begin(), vec.end());
  steady_clock::time_point end = steady_clock::now();

  cout << (is_sorted(vec.begin(), vec.end()) ? "" : "not ") << "sorted " << endl;
  duration<double> span = duration_cast<duration<double>>(end - start);
  cout << "Took: " << span.count() << " seconds" << endl;

  return 0;
}