#include <stdio.h>
#include <math.h>
#include <sys/time.h>
#include <string.h>
#include <pthread.h>
#define MAXThreadsNum 32  //允許啟動的最大線程數量

int TimeSteps=0; 
int thread_num=0 ;
int Ndata = 40 ;
int data[2000]={12,54,77,3,9,16,33,82,11,24,12,54,65,23,77,66,44,34,23,87,14,53,74,86,95,53,16,70,10,20,30,40,50,60,88,55,33,45,96,91} ;
int newdata[2000] ;
int countstart[40],countend[40] ;
void *quicksort(void *);
int main(int argc, char** argv )
{
    
      timeval start, end;
      char *pStr;
      gettimeofday(&start, NULL);
      int threadID[MAXThreadsNum];
      pthread_t threads[MAXThreadsNum];
      double run_time;
      int i ;
      for( i=1; i<argc; i++) {
		pStr=strstr(argv[i], "-p=");
		if ( pStr==NULL ) continue;
		sscanf(pStr, "-p=%d", &thread_num);
	}
      if(thread_num<2) {
	  printf("Please input the number of threads to be created by specifying -p=num_of_threads, where num_of_threads is a integer greater than 1\n");
	  return 0;
      }
      if(thread_num>MAXThreadsNum) thread_num = MAXThreadsNum;
      //創建線程
	for(i=0; i<thread_num; i++) {
		threadID[i] = i;
		pthread_create(&threads[i],NULL, quicksort, &threadID[i]);
	}

      //等待全部線程結束
	for(i=0; i<thread_num; i++) 
		pthread_join(threads[i],NULL);
      int cnum = 0 ;
      while(cnum <= Ndata)
      {
          int record ;
          int min = 1000000 ;
          for( i = 1 ; i <= thread_num ; i++ )
          {
                if( countstart[i] > countend[i] )
                       continue ;
                if( data[countstart[i]] < min )
                {
                     min = data[countstart[i]] ;
                     record = i ;
                 }
           }
           newdata[cnum++] = data[countstart[record]] ;
           countstart[record]++ ;

      }
      for( i = 0 ; i < Ndata ; i++ )
          printf("%d ",newdata[i]) ;
      gettimeofday(&end, NULL);
      run_time = end.tv_sec - start.tv_sec + (double)(end.tv_usec-start.tv_usec)/1000000.0; 
      printf("runtime is : %f\n", run_time);
}
void swap(int i, int j )
{
    int med = data[i] ;
    data[i] = data[j] ;
    data[j] = med ;
}
void sort( int start,int end )
{
    if( start >= end )
        return ;
    int count = start;
    
    for( int i = start + 1 ; i <= end ; i++ )
    {
        if( data[i] < data[start] )
        {
             swap(i,count+1) ;
             count++ ;
        }
    }
    printf("%d %d %d\n",start,end,count) ;
    swap(count,start) ;
    if( count-1 >= start )
         sort(start,count-1) ;
    if( end >= count+1)
       sort(count+1,end) ;
    return ;
        
}
void *quicksort(void *arg) {
	int myID = *((int*)arg);
       int start,end ;
       start = myID * ( Ndata/thread_num ) ;
       countstart[myID+1] = start ;
       if( myID == thread_num - 1)
           end = Ndata-1 ;
       else end = (myID + 1) * ( Ndata/thread_num ) - 1 ;
       countend[myID+1] = end ;
       sort(start,end) ;
return((void*)NULL);
}