Metrics mergesort(unit *arr, ulen length) {
	Metrics ms = {"mergesort", 0, 0, 1};
	if (length > 1) {
		ulen mid = length / 2;
		Metrics rms = mergesort(arr, mid);
		Metrics lms = mergesort(&arr[mid], length-mid);

		unit *temp = malloc(length * sizeof(unit)); 

		ulen i, l = 0, r = mid;
		for(i=0; i<length && l < mid && r < length; i++, ms.cmp++, ms.ass++) {
			if (arr[l] < arr[r]) {
				temp[i] = arr[l++];
			} else {
				temp[i] = arr[r++];
			}
		}
		if (l < mid)
			memcpy(&temp[i], &arr[l], (length-i) * sizeof(unit));
		if (r < length)
			memcpy(&temp[i], &arr[r], (length-i) * sizeof(unit));

		memcpy(arr, temp, length * sizeof(unit));
		free(temp);

		ms.cmp += lms.cmp + rms.cmp;
		ms.ass += lms.ass + rms.ass + (length - i) + length;
		ms.rec += lms.rec + rms.rec;
	}
	return ms;
}

=== mergesort ===
n          : 100000
n*log(n)   : 1660964
n^2        : 10000000000
calls      : 199999
comparisons: 1536114
assignments: 3337856
runtime    : 0.040000s