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

using namespace std;

void split(int A[], int Asize, int B[], int C[])
{ int Bpos = 0, Cpos = 0;
  bool Bturn = true;
  for (int Apos = 0; Apos < Asize; Apos += 1)
  { if (Bturn)
    { B[Bpos] = A[Apos];
      Bpos += 1; }
    else
    { C[Cpos] = A[Apos];
      Cpos += 1; }
    Bturn = ! Bturn; } }

void merge(int X[], int Xsize, int Y[], int Ysize, int Z[])
{ int Xpos = 0, Ypos = 0, Zpos = 0;
  while (Xpos < Xsize && Ypos < Ysize)
  { if (X[Xpos] < Y[Ypos])
    { Z[Zpos] = X[Xpos];
      Xpos += 1; }
    else
    { Z[Zpos] = Y[Ypos];
      Ypos += 1; }
    Zpos += 1; }
  while (Xpos < Xsize)
  { Z[Zpos] = X[Xpos];
    Zpos += 1;
    Xpos += 1; }
  while (Ypos < Ysize)
  { Z[Zpos] = Y[Ypos];
    Zpos += 1;
    Ypos += 1; } }

void print(string s, int A[], int size)
{ cout << s << ":";
  for (int i = 0; i < size; i += 1)
    cout << " " << A[i];
  cout << "\n"; }

bool identical(int X[], int Y[], int size)
{ for (int i = 0; i < size; i += 1)
    if (X[i] != Y[i])
      return false;
  return true; }

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 sort(int W[], int size) // Selection sort
{ int end = size - 1;
  for (int begin = 0; begin < end; begin += 1)
  { int smallestpos = begin;
    for (int j = begin; j <= end; j += 1)
      if (W[j] < W[smallestpos])
        smallestpos = j;
    swap(W[smallestpos], W[begin]); } }

int main(int argc, char * argv[])
{ string which_sort = argv[1];
  int N = atoi(argv[2]);
  srandomdev();
  int * A = new int[N];
  int * copy = new int[N];

  int start = 0;
  for (int i = 0; i < N ; i += 1)
  { int r = random() % 10;
    start += r;
    A[i] = start;
    copy[i] = start; }

  for (int i = 0; i < 4 * N; i += 1)
  { int r1 = random() % N;
    int r2 = random() % N;
    swap(A[r1], A[r2]); }

  double t1 = get_cpu_time();

  if (which_sort == "s")
    sort(A, N);
  else
  { int Bsize = N - N/2, Csize = N/2;
    int * B = new int[Bsize];
    int * C = new int[Csize];
    split(A, N, B, C);
    sort(B, Bsize);
    sort(C, Csize);
    merge(B, Bsize, C, Csize, A);
    delete []  B;
    delete [] C; }

  double t2 = get_cpu_time();
  cout << "It took " << t2 - t1 << " Seconds\n";

  if (identical(A, copy, N))
    cout << "Correct sort\n";
  else
    cout << "FAILED\n";
}