#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <boost/thread/thread.hpp>
#define DEBUG 0
#include <iomanip>

using namespace std;

unsigned int tab_size;

//======= NAGLOWKI ============


const int maxw = 100;
const int minw = 0;
int * tab;
int * temptab;
int * tab2;
int pocz1=0, sr1=0, kon1=0;
bool useboost = 1;

void prepare();
void wypisz(int* tablica);
void clear_temp();

inline void merge(int pocz, int sr, int kon);
inline void mergesort(int pocz, int kon);


inline void bmerge(int pocz, int sr, int kon);
inline void bmergesort(int pocz, int kon);
void wat1();
void wat2();

//=============================

int main(){
time_t czas1, czas2;
cout<<"Rozmiar tablicy: "<<endl;
cin >> tab_size;
tab = new int[tab_size];
temptab = new int[tab_size];
tab2 = new int[tab_size];

prepare();

#if DEBUG == 1
cout<<"Tablica przed posortowaniem: "<<endl;
wypisz(tab);
#endif

//=========== wersja sekwencyjna
czas1 = clock();
mergesort(0, tab_size-1);
czas2 = clock();
double czas = double(czas2-czas1)/CLOCKS_PER_SEC;
cout<<"Czas sortowania tablicy sekwencyjnie: "<<setprecision(6)<<czas<<" s."<<endl;
//==============================

#if DEBUG == 1
cout<<"Tablica posortowana: "<<endl;
wypisz(tab);
#endif





#if DEBUG == 1
cout<<"Tablica przed posortowaniem: "<<endl;
wypisz(tab2);
#endif

//=========== wersja watkowa
czas1 = clock();
bmergesort(0, tab_size-1);
czas2 = clock();
czas = double(czas2-czas1)/CLOCKS_PER_SEC;
cout<<"Czas sortowania tablicy w 2 watkach: "<<czas<<" s."<<endl;
//==============================

#if DEBUG == 1
cout<<"Tablica posortowana: "<<endl;
wypisz(tab2);
#endif


delete tab;
delete temptab;
delete tab2;
}


void prepare(){

srand((unsigned int)time(NULL));
//zapelnianie tablicy losowymi liczbami z pewnego zakresu
for (unsigned int i=0; i<tab_size; i++){
tab[i] = rand()%(maxw-minw+1)+minw;
tab2[i] = tab[i];
}
}

void wypisz(int* tablica){

for (unsigned int i=0; i<tab_size; i++){
cout<<tablica[i]<<", ";
}
cout<<endl<<endl;
}

void merge(int pocz, int sr, int kon)
{
  int i,j,q;
  for (i=pocz; i<=kon; i++) temptab[i]=tab[i];  // Skopiowanie danych do tablicy pomocniczej
  i=pocz; j=sr+1; q=pocz;                 
  while (i<=sr && j<=kon) {
    if (temptab[i]<temptab[j])
        tab[q++]=temptab[i++];
    else
        tab[q++]=temptab[j++];
  }
  while (i<=sr) tab[q++]=temptab[i++];
}


void mergesort(int pocz, int kon)
{
  int sr;
  if (pocz<kon) {
    sr=(pocz+kon)/2;
    mergesort(pocz, sr);    // Dzielenie lewej czesci
    mergesort(sr+1, kon);   // Dzielenie prawej czesci
    merge(pocz, sr, kon);   // laczenie czesci lewej i prawej
  }
}


//========================================
//   FUNKCJE DOTYCZACE WATKOW
//========================================

void bmerge(int pocz, int sr, int kon)
{
  int i,j,q;
  for (i=pocz; i<=kon; i++) temptab[i]=tab2[i];  // Skopiowanie danych do tablicy pomocniczej
  i=pocz; j=sr+1; q=pocz;                 
  while (i<=sr && j<=kon) {
    if (temptab[i]<temptab[j])
        tab2[q++]=temptab[i++];
    else
        tab2[q++]=temptab[j++];
  }
  while (i<=sr) tab2[q++]=temptab[i++];
}


void bmergesort(int pocz, int kon)
{
  if (pocz<kon) {
	int sr=(pocz+kon)/2;

	if(useboost == 1)
	{
        sr1 = sr;
        pocz1 = pocz;
	kon1 = kon;
	useboost = 0;
	boost::thread w1(&wat1);
	boost::thread w2(&wat2);
	w1.join();
	w2.join();
	} else
	{


	bmergesort(pocz, sr);    // Dzielenie lewej czesci
	bmergesort(sr+1, kon);   // Dzielenie prawej czesci
	}
	bmerge(pocz, sr, kon);   // laczenie czesci lewej i prawej
	}
    }    
  


void wat1(){
bmergesort(pocz1, sr1);
}

void wat2(){
bmergesort(sr1+1, kon1); 
}