# g++ -lpthread project1-6b.cc -o project1-6b
#
#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
#include <pthread.h>

#define ARRAYSIZE 10000000
#define NUMTHREADS 10000000

void  quickSort(int* array, int first, int last, int numThreads = 1);
void* quickSort(void*);
int partition(int* array, int first, int last, int pivotIndex);


struct quickSort_args
{
	int* array;
	int first;
	int last;
	int numThreads;
};


int main()
{
	int* myArray;
	int i,j;
	timeval t1,t2;
	
	printf("\nSorting an array of %d integers using %d threads...\n\n",ARRAYSIZE,NUMTHREADS);

	myArray = new int[ARRAYSIZE];


	//gettimeofday(&t1,NULL);
	//srand(t1.tv_usec);
	srand(8675309);
	for(i=0;i<ARRAYSIZE;i++)
	{
		myArray[i] = rand() % 65536;
	}

	
	//for(i=0;i<ARRAYSIZE;i++)
	//{
	//printf("%d ",myArray[i]);
	//}
	gettimeofday(&t1,NULL);

	quickSort(myArray,0,ARRAYSIZE-1, NUMTHREADS);

	gettimeofday(&t2,NULL);
	
	//for(i=0;i<ARRAYSIZE;i++)
	//{
	//	printf("%d ",myArray[i]);
	//}

	printf("TIME BEFORE CALLING mergeSort(): %10d.%06d sec\n",t1.tv_sec,t1.tv_usec);
	printf("TIME AFTER  CALLING mergeSort(): %10d.%06d sec\n",t2.tv_sec,t2.tv_usec);
	printf("==========================================================\nRUNNING TIME OF     mergeSort(): %10d.%06d sec\n\n\n",((t2.tv_usec-t1.tv_usec)<0)?(t2.tv_sec-t1.tv_sec-1):(t2.tv_sec-t1.tv_sec),      t2.tv_usec-t1.tv_usec<0?1000000-(t1.tv_usec-t2.tv_usec):t2.tv_usec-t1.tv_usec);

	delete [] myArray;
	return 0;
}


void* quickSort(void* args)
{
	quickSort_args* myArgs;
	myArgs = (quickSort_args*) args;
	quickSort(myArgs->array, myArgs->first, myArgs->last, myArgs->numThreads);
	return NULL;
}




void quickSort(int* array, int first, int last, int numThreads)
{
	int pivotIndex;

	pthread_t* t1;
	pthread_t* t2;
	pthread_attr_t* attr;
	quickSort_args* a1;
	quickSort_args* a2;

	if(first<last)
	{

		pivotIndex = partition(array,first,last,last);

		if(numThreads%2 != 0)
			numThreads--;

		if(numThreads>=2)
		{
			numThreads = numThreads-2;
			t1 = new pthread_t;
			t2 = new pthread_t;
			attr = new pthread_attr_t;
			a1 = new quickSort_args;
			a2 = new quickSort_args;
	
			pthread_attr_init(attr);
			pthread_attr_setscope(attr,PTHREAD_SCOPE_SYSTEM);
			pthread_attr_setdetachstate(attr,PTHREAD_CREATE_JOINABLE);

			a1->array = array;
			a1->first = first;
			a1->last = pivotIndex-1;

			a2->array = array;
			a2->first = pivotIndex+1;
			a2->last = last;
			if((numThreads/2)%2 == 0)
			{
				a1->numThreads = numThreads/2;
				a2->numThreads = numThreads/2;
			}
			else
			{
				a1->numThreads = numThreads/2 +1;
				a2->numThreads = numThreads/2 -1;
			}

			//printf("Creating 2 new threads.\n");
			pthread_create(t1, attr, quickSort,(void*)a1);
			pthread_create(t2, attr, quickSort,(void*)a2);
			pthread_join(*t1,NULL);
			pthread_join(*t2,NULL);
			
			delete t1;
			delete t2;
			delete attr;
			delete a1;
			delete a2;
		}
		else
		{
			quickSort(array,first,pivotIndex-1);
			quickSort(array,pivotIndex+1,last);
		}
	}
}

int partition(int* array, int first, int last, int pivotIndex)
{
	int temp;
	int writeIndex;
	int pivotValue;

	

	pivotValue = array[pivotIndex];
	array[pivotIndex] = array[last];
	array[last] = pivotValue;

	writeIndex = first;
	for(int i = first; i < last;i++)
	{
		if(array[i] <= pivotValue)
		{
			temp = array[i];
			array[i] = array[writeIndex];
			array[writeIndex++] = temp;
		}
	}
	
	temp = array[writeIndex];
	array[writeIndex] = array[last];
	array[last] = temp;
	
	return writeIndex;
}