Metrics quicksort(unit *arr, ulen length) {
	Metrics ms = {"quicksort", 0, 0, 1};
	if (length > 1) {
		unit pivot = arr[0];

		unit *left = malloc(length * sizeof(unit));
		unit *right = malloc(length * sizeof(unit));

		ulen l = 0, r = 0;
		for(ulen i=1; i<length; i++, ms.cmp++, ms.ass++) {
			if (arr[i] < pivot) {
				left[l++] = arr[i];
			} else {
				right[r++] = arr[i];
			}
		}

		arr[l] = pivot;
		memcpy(arr, left, l * sizeof(unit));
		memcpy(&arr[l+1], right, r * sizeof(unit));

		free(left);
		free(right);

		Metrics lms = quicksort(arr, l);
		Metrics rms = quicksort(&arr[l+1], r);

		ms.cmp += lms.cmp + rms.cmp;
		ms.ass += lms.ass + rms.ass + length + 1;
		ms.rec += lms.rec + rms.rec;
	}
	return ms;
}

=== quicksort ===
n          : 100000
n*log(n)   : 1660964
n^2        : 10000000000
calls      : 133599
comparisons: 1923150
assignments: 3979898
runtime    : 0.040000s