#include <iostream>
#include <time.h>
#include <cmath>
#include <sys/resource.h>

using namespace std;

double get_cpu_time()
{ struct rusage ruse;
  getrusage(RUSAGE_SELF, &ruse);
  return ruse.ru_utime.tv_sec + ruse.ru_utime.tv_usec / 1000000.0 + 
         ruse.ru_stime.tv_sec + ruse.ru_stime.tv_usec / 1000000.0; }

void split(int X[], int Xsize, int Y[], int Z[])
// splits X into Y and Z
{ int xp = 0, yp = 0, zp = 0;
  while (true)
  { if (xp == Xsize)
      break;
    int item = X[xp];
    Y[yp] = item;
    xp += 1;
    yp += 1;

    if (xp == Xsize)
      break;
    item = X[xp];
    Z[zp] = item;
    xp += 1;
    zp += 1; } }

void merge(int A[], int Asize, int B[], int Bsize, int C[])
{ // A and B are already sorted, want C to be sorted
  int ap = 0, bp = 0, cp = 0;
  while (ap < Asize && bp < Bsize)
  { if (A[ap] < B[bp])
    { C[cp] = A[ap];
      cp += 1;
      ap += 1; }
    else
    { C[cp] = B[bp];
      cp += 1;
      bp += 1; } }
  while (ap < Asize)
  { C[cp] = A[ap];
    cp += 1;
    ap += 1; }
  while (bp < Bsize)
  { C[cp] = B[bp];
    cp += 1;
    bp += 1; } }

void sort(int M[], int Msize)
{ if (Msize <= 1)
    return;
  int Qsize = Msize / 2;       // the smaller half
  int Psize = Msize - Qsize;   // the larger half
  int * P = new int[Psize];
  int * Q = new int[Qsize];
  split(M, Msize, P, Q);

  sort(P, Psize);
  sort(Q, Qsize);

  merge(P, Psize, Q, Qsize, M);
  delete [] P;
  delete [] Q; }

int main(int argc, char * argv[])
{ int N = atoi(argv[1]);
  int * D = new int[N];
  int * E = new int[N];

  srandomdev();
  int start = random() % 20;
  for (int i = 0; i < N; i += 1)
  { D[i] = start;
    E[i] = start;
    start += random() % 20; }

  for (int i = 0; i < 2 * N; i += 1)
  { int pos1 = random() % N;
    int pos2 = random() % N;
    swap(D[pos1], D[pos2]); }

  double t1 = get_cpu_time();
  sort(D, N);
  double t2 = get_cpu_time();
  double t = t2 - t1;
  cout << "It took " << t << " seconds, k = " << t / (N * log2(N)) << "\n";

  bool same = true;
  for (int i = 0; i < N; i += 1)
    if (D[i] != E[i])
    { same = false;
      break; }

  if (same)
    cout << "Successful\n";
  else
    cout << "The sort went wrong\n"; }