merge.c

#include <stdlib.h>
#include <string.h>
typedef unsigned int uint;

static void split_array(int array[], uint len, int **left, uint *llen, int **right, uint *rlen) {
	*llen = *rlen = len / 2;
	if (*llen + *rlen < len) {
		*llen = *llen + 1;
	}
	size_t lsize = *llen * sizeof (int);
	size_t rsize = *rlen * sizeof (int);
	*left = malloc(lsize);
	*right = malloc(rsize);
	memcpy(*left, array, lsize);
	memcpy(*right, array + *llen, rsize);
}

static int *merge_arrays(int left[], uint llen, int right[], uint rlen) {
	int *merged;
	merged = malloc((llen + rlen) * sizeof (int));
	uint idx = 0;
	while (llen > 0 && rlen > 0) {
		int a = left[0];
		int b = right[0];
		if (a <= b) {
			merged[idx++] = a;
			left++;
			llen--;
		} else {
			merged[idx++] = b;
			right++;
			rlen--;
		}
	}
	if (llen > 0) {
		memcpy(merged + idx, left, llen * sizeof (int));
	} else if (rlen > 0) {
		memcpy(merged + idx, right, rlen * sizeof (int));
	}
	return merged;
}

int *sort_array(int array[], uint len) {
	int *sorted;
	if (len == 1) {
		sorted = malloc(sizeof (int));
		sorted[0] = array[0];
	} else if (len == 2) {
		sorted = malloc(2 * sizeof (int));
		int a = array[0];
		int b = array[1];
		if (a < b) {
			sorted[0] = a;
			sorted[1] = b;
		} else {
			sorted[0] = b;
			sorted[1] = a;
		}
	} else {
		int *left, llen, *right, rlen;
		split_array(array, len, &left, &llen, &right, &rlen);
		int *left_sorted = sort_array(left, llen);
		int *right_sorted = sort_array(right, rlen);
		free(left);
		free(right);
		sorted = merge_arrays(left_sorted, llen, right_sorted, rlen);
		free(left_sorted);
		free(right_sorted);
	}
	return sorted;
}