#include <stdio.h>

#define OP 0
#define AF 1

void displayRij(char *text, int depth, int *rij, int length) {
	int i;
	for (i = 0; i < depth; i++) {
		printf(" ");
	}
	printf("%s: ", text);
	for (i = 0; i < length; i++) {
		printf("%c ", 'a' + rij[i] - 1);
	}
	printf("\n");
}


void minmax(int *a, int* b, int kant) {
	int tmp = *a;
	if (	(kant == OP && tmp > *b) ||
		(kant == AF && tmp < *b)) {
		*a = *b;
		*b = tmp;
	}
}

void merge(int depth, int *rij, int length, int kant) {
	int dx = length / 2;
	int i = 0;
	displayRij("MERGE", depth, rij, length);
	for (; i < dx; i++) {
		minmax(&rij[i], &rij[i+dx], kant);
	}
	displayRij("MERGERESULT", depth, rij, length);
}

void sort(int depth, int *rij, int length, int kant) {
	int dx = length / 2;
	displayRij("SORT", depth, rij, length);
	if (length == 2) {
		minmax(&rij[0], &rij[1], kant);
		return;
	}
	sort(depth+1, rij, dx, OP);
	sort(depth+1, &rij[dx], dx, AF);
	merge(depth+1, rij, length, kant);
	sort(depth+1, rij, dx, kant);
	sort(depth+1, &rij[dx], dx, kant);
}

void generateTestData(int *rij, int length) {
	int i;
	srand(100);
	for (i = 0; i < length; i++) {
		rij[i] = lrand48() >> 58;
	}
}

int main(int argc, char **argv) {
	int length = 8;
	//int *testrij = (int*)malloc(sizeof(int) * length); //{8, 1, 7, 2, 6, 3, 5, 4};
	int testrij[] = {3, 4, 2, 8, 5, 7, 6, 1};
	//generateTestData(testrij, length);
	displayRij("START", 0, testrij, length);
	sort(0, testrij, length, OP);
	displayRij("END", 0, testrij, length);
}