#include <u.h>
#include <libc.h>
	
int
mergesort1(int uniq, char *a, int r, int width, int (*compare)(void*, void*), char *b)
{
	int m, n0, n1, i, j, k, e, c;
	if(r <= width)
		return r;
	m = ((r/width-1)/2 + 1) * width;
	n0 = mergesort1(uniq, a, m, width, compare, b);
	n1 = mergesort1(uniq, a+m, r-m, width, compare, b);
	memcpy(b, a, n0);
	memcpy(b+n0, a+m, n1);
	e = n0+n1;
	i = 0;
	j = n0;
	k = 0;
	for(; i < n0 && j < e; k += width){
		c = (*compare)(b+i, b+j);
		if(c > 0){
			memcpy(a+k, b+j, width);
			j += width;
		}else{
			memcpy(a+k, b+i, width);
			i += width;
			if(c == 0 && uniq)
				j += width;
		}
	}
	if(i < n0){
		memcpy(a+k, b+i, n0-i);
		k += n0-i;
	}else if(j < e){
		memcpy(a+k, b+j, e-j);
		k += e-j;
	}
	return k;
}

int
mergesort(int uniq, void *a, long n, long width, int (*compare)(void*, void*))
{
	void *b;
	n *= width;
	b = malloc(n);
	if(b == nil)
		return -1;
	n = mergesort1(uniq, a, n, width, compare, b);
	free(b);
	return n / width;
}