#include <stdio.h>
#include <stdlib.h>
void Merge(int *tab, int * tmp, int a , int b) {
	int i,j,k,sr;
	sr = (a+b)/2;

	for(i = a ; i <= b; i++) tmp[i] = tab[i];

	i = k = a;
	j = sr;

	while(i <= sr && j <= b) {
		if(tmp[i] < tmp[j]) {
			tab[k++] = tmp[i++];
		} else {
			tab[k++] = tmp[j++];
		}
	}
	while(i <= sr) {
			tab[k++] = tmp[i++];
	}
}

void DivideMerge(int * tab, int * tmp, int a, int b) {
	int sr = (a+b)/2;
	if(a < b) {
		DivideMerge(tab, tmp, a, sr);
		DivideMerge(tab, tmp, sr+1, b);
		Merge(tab, tmp ,a ,b );
	}
}

void MergeSort(int * t, int n) {
	int * tmp = (int*) malloc ( sizeof(int) * n);
	DivideMerge(t, tmp, 0, n-1);
	free(tmp);
}

void Wypisz(int * t, int n) {
	int i;
	for( i = 0 ; i < n ; i++) {
		printf("%d ", t[i]);
	}
	printf("\n");
}


void Quick(int * t, int a, int b) {
	int i, j, x, tmp;
	i = a;
	j = b;
//	int losowa = rand() % (b-a+1) + a;
	x = t[b];
	do {
		while(t[i] < x)
			i++;
		while(t[j] > x)
			j--;

		if(i <= j) {
			tmp = t[i];
			t[i] = t[j];
			t[j] = tmp;

			i++;
			j--;
		}
	}while(i <= j);
	if(a < j) Quick(t, a, j);
	if(b > i) Quick(t, i, b);
}

void QuickSort(int * t, int n) {
	Quick(t, 0, n-1);
}

int main(int argc, char *argv[]) {
	int n = 20, i;
	int * tab = (int*) malloc(sizeof(int) * n);
	for(i = 0 ; i < n; i++ ) tab[i] = rand()%100;
	Wypisz(tab, n);
	QuickSort(tab,n);
	Wypisz(tab, n);

	free(tab);
	return 0;
}