// Threaded quicksort implementation, serially sorting below a threshold.
// compile with: gcc -O2 -Wall -pthread quicksort-threads-threshold.c -o quicksort-threads-threshold -DN=10000000

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <pthread.h>


#define CUTOFF 10

#define SERIAL_THRESHOLD 100000


void get_walltime(double *wct) {
  struct timeval tp;
  gettimeofday(&tp,NULL);
  *wct = (double)(tp.tv_sec+tp.tv_usec/1000000.0);
}


void inssort(double *a,int n) {
int i,j;
double t;
  
  for (i=1;i<n;i++) {
    j = i;
    while ((j>0) && (a[j-1]>a[j])) {
      t = a[j-1];  a[j-1] = a[j];  a[j] = t;
      j--;
    }
  }

}


int partition(double *a,int n) {
int first,last,middle;
double t,p;
int i,j;

  // take first, last and middle positions
  first = 0;
  middle = n/2;
  last = n-1;  
  
  // put median-of-3 in the middle
  if (a[middle]<a[first]) { t = a[middle]; a[middle] = a[first]; a[first] = t; }
  if (a[last]<a[middle]) { t = a[last]; a[last] = a[middle]; a[middle] = t; }
  if (a[middle]<a[first]) { t = a[middle]; a[middle] = a[first]; a[first] = t; }
    
  // partition (first and last are already in correct half)
  p = a[middle]; // pivot
  for (i=1,j=n-2;;i++,j--) {
    while (a[i]<p) i++;
    while (p<a[j]) j--;
    if (i>=j) break;

    t = a[i]; a[i] = a[j]; a[j] = t;      
  }
  
  // return position of pivot
  return i;
}


void serial_quicksort(double *a,int n) {
int i;
  // check if below cutoff limit
  if (n<=CUTOFF) {
    inssort(a,n);
    return;
  }
  
  // partition into two halves
  i = partition(a,n);
   
  // recursively sort halves
  serial_quicksort(a,i);
  serial_quicksort(a+i,n-i);
  
}


// struct of info passed to each thread
struct thread_params {
  double *a;
  int n;
};


// forward declaration of thread work function
void *work(void *);


void threaded_quicksort(double *a,int n) {
int i;
pthread_t sub_thread;
struct thread_params sub_tparm;

  // check if below serial threshold limit
  if (n<=SERIAL_THRESHOLD) {
    serial_quicksort(a,n);
    return;
  }
  
  // partition into two halves
  i = partition(a,n);
   
  // launch sub thread to handle left half
  sub_tparm.a = a;
  sub_tparm.n = i;
  if (pthread_create(&sub_thread,NULL,work,&sub_tparm)!=0) {
    printf("Error in thread creation!\n");
    exit(1);
  }

  // handle right part ourselves
  threaded_quicksort(a+i,n-i);
  
  // join subthread
  pthread_join(sub_thread,NULL);
      
}


// threaded function (should be void * returning by specs)
void *work(void *args) {

  struct thread_params *parm = (struct thread_params *)args;
  double *a = parm->a;
  int n = parm->n; 

  threaded_quicksort(a,n);
    
  // exit and let be joined
  pthread_exit(NULL);   
}


int main() {
double ts,te;
double *a;
int i;
 
  a = (double *)malloc(N*sizeof(double));
  if (a==NULL) {
    printf("error in malloc\n");
    exit(1);
  }

  // fill array with random numbers
  srand(0);
  for (i=0;i<N;i++) {
    a[i] = (double)rand()/RAND_MAX;
  }

  // get starting time (double, seconds) 
  get_walltime(&ts);

  threaded_quicksort(a,N);
  
  // get ending time
  get_walltime(&te);

  // check sorting
  for (i=0;i<(N-1);i++) {
    if (a[i]>a[i+1]) {
      printf("Sort failed!\n");
      break;
    }
  }  

  free(a);
  
  printf("Exec Time (sec) = %f\n",te-ts);
  
  return 0;
}