#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <stdint.h>

#define DO_PRINT 0

void printArr(int *arr, size_t len) {
	printf("{");
	for(int i = 0; i < len; i++) {
		printf(" %d%s", arr[i], i+1 == len ? " " : ",");
	}
	printf("}\n");
}

int *genArr(size_t len, int div) {
	/* Make array */
	int *arr = (int *) malloc(len * sizeof(int));

	if( arr == NULL) {
		return NULL;
	}

	/* Fill it with random */
	while( len-- ) {
		arr[len] = div - (rand() % (div*2));
	}

	return arr;

}

int mergeSort(int *arr, size_t len) {
	/* Check if len is one(then it's sorted */
	if (len <= 1) {
		return 0;
	}
	/* Calculate array sizes */
	size_t q = len/2;
	size_t rl = len-q;

	/* Make arrays */
	int *left = (int *) malloc(q * sizeof(int));
	if( left == NULL ) {
		return 1;
	}
	int *right = (int *) malloc(rl * sizeof(int));
	if( right == NULL ) {
		return 1;
	}

	/* Copy data */
	memcpy(left, arr, q * sizeof(int));
	memcpy(right, arr + q, rl * sizeof(int));

	/* Sort each */
	mergeSort(left, q);
	mergeSort(right, rl);

	/* Merge them into arr */
	for(int i=0, j=0, k = 0; k < len; k++) {
		if( i < q && ( j == rl || left[i] <= right[j] ) ) {
			arr[k] = left[ i++ ];
		} else {
			arr[k] = right[ j++ ];
		}
	}

	/* Free the pointers */
	free(left);
	free(right);

	return 0;
}

void test(size_t len) {

	int *a = genArr(len, len);

#if DO_PRINT == 1
	printArr(a, len);
	printf("\n\n");
#endif

	clock_t begin = clock();
	mergeSort(a, len);
	clock_t end = clock();

#if DO_PRINT == 1
	printArr(a, len);
#endif

	clock_t diff = end - begin;
	printf("Sorting %d long array took %d : %f s\n", len, diff, (double)diff/CLOCKS_PER_SEC);

	free(a);
}

void bench() {

	size_t len = SIZE_MAX;

	srand((unsigned) time(NULL));
	for (int i = 1; i < len; i *= 2) {
		test(i);
	}
}

int main(void) {

	bench();

	return 0;
}