#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include <string.h>
#define cast(type, expr) (type)(expr)
#define array_size(arr) (sizeof(arr) / sizeof(arr[0]))

typedef unsigned int uint;
typedef int elem_t;

void* checked_malloc(size_t size, const char* for_what)
{
	void* ptr = malloc(size);
	if (!ptr)
	{
		fprintf(stderr, "Memory allocation for %s failed", for_what);
		exit(1);
	}
	return ptr;
}

void _msort(uint n, elem_t* src, elem_t* dst, bool inplace)
{
	assert(n != 0);
	if (n == 1)
	{
		if (!inplace) dst[0] = src[0];
		return;
	}

	uint avg = n/2;
	uint nL = avg, nR = n - avg;
	_msort(nL, src, dst, !inplace);
	_msort(nR, src + avg, dst + avg, !inplace);

	elem_t* tmp = inplace ? dst : src;
	elem_t* target = inplace ? src : dst;
	elem_t* L = tmp, *R = tmp + nL;
	for (; nL && nR; target++)
	{
		if (*L < *R)
		{
			*target = *L;
			L++, nL--;
		} else
		{
			*target = *R;
			R++, nR--;
		}
	}
	memcpy(target, nL ? L : R, (nL ? nL : nR) * sizeof(elem_t));
}

void merge_sort(uint n, elem_t* a)
{
	if (n <= 1) return;
	elem_t* tmp = cast(elem_t*, checked_malloc(n * sizeof(elem_t), "merge_sort buffer"));
	_msort(n, a, tmp, true);
	free(tmp);
}

void print_array(const char *desc, uint n, elem_t* arr)
{
	printf("%s", desc);
	for (uint i = 0; i < n; i++)
		printf("%i ", arr[i]);
	printf("\n");
}

int main(int argc, char* argv[])
{
	elem_t arr[] = {5, 6, 1, 3, 9, 8, 112, 4, 66, -5};
	print_array("Source array: ", array_size(arr), arr);

	printf("Sorting... ");
	merge_sort(array_size(arr), arr);
	printf("Done\n");

	print_array("Sorted array: ", array_size(arr), arr);
	return 0;
}