#include<iostream>
#include<Windows.h>
#include <cstdlib>
#include <ctime>

#define SIZE 20
int tab[SIZE];

//deklaracja struktury sprawia, ze do nowego watku wystarczy przekazac jeden argument
struct Indexes {
	int start;
	int end;
};

//funkcja zapelniajaca podana tablice losowymi liczbami
void fillWithRandom(int* table, int max){
	for (int i = 0; i < SIZE; i++){
		table[i] = rand() % max;
	}
}

void Sort(int start, int end) {
	int centre = (start + end) / 2; //okreslanie srodka tablicy

	int i = start, j = centre + 1, q = start;
	int tabtmp[SIZE];

	for (int a = start; a <= end; a++)
		tabtmp[a] = tab[a];

	//przepisywanie liczb z tablicy tymczasowej, do wlasciwej
	while (i <= centre && j <= end) {
		if (tabtmp[i] < tabtmp[j]){
			tab[q] = tabtmp[i];
			++q; ++i;
		}else{
			tab[q] = tabtmp[j];
			++q; ++j;
		}
	}

	for (; i <= centre; ++q,++i){
		tab[q] = tabtmp[i];
	}
}

DWORD WINAPI MergeSort(void *indexes) {

	//rzutowanie z typu void
	Indexes *indexesTmp = (Indexes*) indexes;

	if (indexesTmp->start >= indexesTmp->end) //jesli algorytm doszedl do konca tablicy, zakoncz
		return 0;

	int centre = (indexesTmp->end + indexesTmp->start) / 2; //okreslanie srodka tablicy
	HANDLE h[2]; //deklaracja dojscia
	DWORD ThreadId; //id watku

	Indexes leftIndex;
	HANDLE leftHandle;
	leftIndex = { indexesTmp->start, centre };
	leftHandle = CreateThread(NULL, 0, MergeSort, &leftIndex, 0, &ThreadId); //utworzenie watku dla pierwszej polowy

	Indexes rightIndex;
	HANDLE rightHandle;
	rightIndex = { centre + 1, indexesTmp->end };
	rightHandle = CreateThread(NULL, 0, MergeSort, &rightIndex, 0, &ThreadId); //utworzenie watku dla drugiej polowy

	//zapobiega bledom
	HANDLE handles[2] = { leftHandle, rightHandle };
	WaitForMultipleObjects(2, handles, TRUE, INFINITE);

	//wywolanie funkcji sortujacej
	Sort(indexesTmp->start, indexesTmp->end);

	return 0;
}


int main() {
	srand(time(NULL));
	fillWithRandom(tab,500);
	Indexes indexes = { 0, SIZE - 1 }; //okreslanie indeksow pozycji dla poczatkowej tablicy
	MergeSort(&indexes);
	for (int i = 0; i < SIZE; i++)
		std::cout << tab[i] << " ";
	getchar();
	return 0;
}