#include <iostream>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <string>
#include <algorithm>
#include "Timer.cpp"

using namespace std;

int *stworz(int *tablica, int rozmiar);
void wyswietl(int *tablica, int rozmiar);

void zamien(int &a, int &b);
void babelkowe(int *tablica, int rozmiar);
void wstawianie(int *tablica, int rozmiar);

void scalanie(int *tablica, int lewy, int prawy);
void scal(int *tablica, int lewy, int srodek, int prawy);

void scal(int *tablica, int start, int srodek, int koniec);
void scalanie(int *tablica, int start, int koniec);

int main(){
	srand(time(NULL));
	Timer timer;
	const int rozmiar = 1E7;
	int *tablica = new int[rozmiar];
		tablica = stworz(tablica, rozmiar);
		timer.start_counter();
		scalanie(tablica, 0, rozmiar);
		timer.stop_counter();
		cout << timer.get_elapsed_time() << endl;
		system("pause");
}

int *stworz(int *tablica, int rozmiar){
	const int min = 50;
	const int maks = 100;
	for (int i = 0; i < rozmiar; i++){
		tablica[i] = (std::rand() % maks - min) + min;
	}
	return tablica;
}

void wyswietl(int *tablica, int rozmiar){
	for (int i = 0; i < rozmiar; i++){
		cout << tablica[i] << " ";
	}
	cout << " "; system("pause"); cout << endl;
}

void zamien(int &a, int &b){
	int tmp = b;
	b = a;
	a = tmp;
}

void babelkowe(int *tablica, int rozmiar){
	bool wyz;
	do{
		wyz = false;
		for (int i = 0; i < rozmiar - 1; ++i) {
			if (tablica[i] > tablica[i + 1]) {
				zamien(tablica[i], tablica[i + 1]);
				wyz = true;
			}
		}
	} while (wyz);
}

void wstawianie(int *tablica, int rozmiar){
	int temp, j;
	for (int i = 1; i < rozmiar; i++)
	{
		temp = tablica[i];

		for (j = i - 1; j >= 0 && tablica[j] > temp; j--)
			tablica[j + 1] = tablica[j];

		tablica[j + 1] = temp;
	}
}

void scal(int *tablica, int start, int srodek, int koniec)
{
	int *tab_pom = new int[(koniec - start)];
	int i = start, j = srodek + 1, k = 0;

	while (i <= srodek && j <= koniec)
	{
		if (tablica[j] < tablica[i])
		{
			tab_pom[k] = tablica[j];
			j++;
		}
		else
		{
			tab_pom[k] = tablica[i];
			i++;
		}
		k++;
	}

	if (i <= srodek)
	{
		while (i <= srodek)
		{
			tab_pom[k] = tablica[i];
			i++;
			k++;
		}
	}
	else
	{
		while (j <= koniec)
		{
			tab_pom[k] = tablica[j];
			j++;
			k++;
		}
	}

	for (i = 0; i <= koniec - start; i++){
		tablica[start + i] = tab_pom[i];
	}
}

void scalanie(int *tablica, int start, int koniec)
{
	int srodek;

	if (start != koniec)
	{
		srodek = (start + koniec) / 2;
		scalanie(tablica, start, srodek);
		scalanie(tablica, srodek + 1, koniec);
		scal(tablica, start, srodek, koniec);
	}
}