#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <math.h>
#define MIN(a,b)  (a < b ? a : b)
int NReps;
int printLevel;
int N;
int* v;
int *vQSort;
int *vNew;
int P;
pthread_barrier_t barrier;


void merge(int source[], int start, int mid, int end, int destination[]) {
	// DO NOT MODIFY
	int iA = start;
	int iB = mid;
	int i;

	for (i = start; i < end; i++)
	{
		if (end == iB || (iA < mid && source[iA] <= source[iB])) {
			destination[i] = source[iA];
			iA++;
		} else {
			destination[i] = source[iB];
			iB++;
		}
	}
}

void compareVectors(int * a, int * b) {
	// DO NOT MODIFY
	int i;
	for(i = 0; i < N; i++) {
		if(a[i]!=b[i]) {
			printf("Sorted incorrectly\n");
			return;
		}
	}
	printf("Sorted correctly\n");
}

void displayVector(int * v) {
	// DO NOT MODIFY
	int i;
	int displayWidth = 2 + log10(v[N-1]);
	for(i = 0; i < N; i++) {
		printf("%*i", displayWidth, v[i]);
		if(!((i+1) % 20))
			printf("\n");
	}
	printf("\n");
}

int cmp(const void *a, const void *b) {
	// DO NOT MODIFY
	int A = *(int*)a;
	int B = *(int*)b;
	return A-B;
}


void getArgs(int argc, char **argv)
{
	if(argc < 5) {
		printf("Not enough paramters: ./program N NReps printLevel P\n");
		exit(1);
	}
	N = atoi(argv[1]);
	NReps = atoi(argv[2]);
	printLevel = atoi(argv[3]);
	P = atoi(argv[4]);
}

void init()
{
	int i;
	v = malloc(sizeof(int) * N);
	vQSort = malloc(sizeof(int) * N);
	vNew = malloc(sizeof(int) * N);
	if(v == NULL) {
		printf("malloc failed!");
		exit(1);
	}

	// generate the vector v with random values
	// DO NOT MODIFY
	srand(42);
	for(i = 0; i < N; i++)
		v[i] = rand()%N;
}

void printPartial()
{
	compareVectors(v, vQSort);
}

void printAll()
{
	displayVector(v);
	displayVector(vQSort);
	compareVectors(v, vQSort);
}

void print()
{
	if(printLevel == 0)
		return;
	else if(printLevel == 1)
		printPartial();
	else
		printAll();
}

void* threadFunction(void *var)
{
	int thread_id = *(int*)var;

	int start_raw = thread_id * ceil((double)N/P);
	int end_raw = MIN(N, (thread_id+1) * ceil((double)N/P));
	int i;
	int width, *aux;
	for (width = 1; width < N; width = 2 * width) {
		int ok = 0;
		int start = start_raw/2/width*2*width;
		int end = end_raw/2/width*2*width;
		for (i = start; i < end; i = i + 2 * width) {
			merge(v, i, i + width, i + 2 * width, vNew);
			ok = 1;
		}
		pthread_barrier_wait(&barrier);
		if (thread_id == 0){
			aux = v;
			v = vNew;
			vNew = aux;
		}
		pthread_barrier_wait(&barrier);
	}


}

int main(int argc, char *argv[])
{
	int i, j;
	getArgs(argc, argv);
	init();

	// make copy to check it against qsort
	// DO NOT MODIFY
	for(i = 0; i < N; i++)
		vQSort[i] = v[i];
	qsort(vQSort, N, sizeof(int), cmp);

	pthread_t tid[P];
	int thread_id[P];
	for(i = 0;i < P; i++)
		thread_id[i] = i;
	int num_threads = P;
	pthread_barrier_init(&barrier, NULL, num_threads);

	for(i = 0; i < P; i++) {
		pthread_create(&(tid[i]), NULL, threadFunction, &(thread_id[i]));
	}

	for(i = 0; i < P; i++) {
		pthread_join(tid[i], NULL);
	}

	pthread_barrier_destroy(&barrier);

	print();

	return 0;
}