// measure CPU and elapsed time 
//
// #ifndef TICTOC_H_
// #define TICTOC_H_

#include <iostream>
#include <ctime>
#include <chrono>
using namespace std;

class tictoc // tic() to start timer, toc() to stop
{
 public: double CPU, Elapsed; tictoc() { CPU=Elapsed=0; tic(); }
  void print(ostream &out=cout) { out<<" CPU: "<<CPU<<endl<<" Elapsed: "<<Elapsed<<endl; }
  void tic() { CPU_start=clock(); Elapsed_start=chrono::high_resolution_clock::now(); }
  void toc() { CPU=(clock()-CPU_start)/CLOCKS_PER_SEC;
    chrono::duration<double> e=chrono::high_resolution_clock::now()-Elapsed_start;
    Elapsed=e.count(); }
 private: double CPU_start; chrono::system_clock::time_point Elapsed_start;
};

// #endif // TICTOC_H_
// measure CPU and elapsed time using qsort() and multiple threads
//
// compile: g++ -std=c++17 -pedantic -Wall -O -pthread
//
#include <iostream>
#include <ctime>   // time()
#include <cstdlib> // rand(), srand(), qsort()
#include <chrono>
#include <thread>
// #include "tictoc.h"
using namespace std;

int compare( const void *v1, const void *v2) // comparison function for qsort()
{
  const int *d1 = (const int *)v1, *d2 = (const int *)v2;

  if( *d1 < *d2) return -1; else if( *d1 > *d2) return +1; else return 0;
}

void quicksort( int d[], size_t n) // qsort() interface
{
  qsort( d, n, sizeof(int), compare);
}

void aprint( const char *msg, int a[], size_t n) // print an array of int
{
  cout << msg << endl; for( size_t i = 0; i < n; ++i) cout << " " << a[i] << endl;
}

int main()
{
  size_t N = 20000000L; cout << "N: "; cin >> N; cout << "N = " << N << endl;

 // allocate array
 //
  int *data = new int[N];

 // fill array with random data
 //
  time_t t0 = time(0); srand(t0); for( size_t i = 0; i < N; ++i) data[i] = rand();

  if( N < 20) aprint( "data:", data, N);

 // time sequential processing
 //
  tictoc tt;

  quicksort( data, N/2); // first half

  quicksort( data+N/2, N-N/2); // second half

  // skip: to complete sorting, the two halves have to be merged...

  tt.toc(); cout << "Sequential:\n";  tt.print();

  if( N < 20) aprint( "data:", data, N);

 // reset data and timer
 //
  srand(t0); for( size_t i = 0; i < N; ++i) data[i] = rand();

  if( N < 20) aprint( "data:", data, N);

  tt.tic();

 // time parallel processing
 //
  thread t1( quicksort, data, N/2), t2( quicksort, data+N/2, N-N/2);

  t1.join(); t2.join();

  tt.toc(); cout << "Parallel:\n";  tt.print();

  if( N < 20) aprint( "data:", data, N);
}

/* sample run on a machine with 2 cores (check: lscpu and /proc/cpuinfo):

N = 20000000
Sequential:
 CPU: 2.96
 Elapsed: 2.95727
Parallel:
 CPU: 2.97
 Elapsed: 1.60984

*/