/* hsort5 -- heap sort implementation of qsort interface  */

#define swap(i, j) {					\
	char *p1 = a + (i)*es, *p2 = a + (j)*es;	\
	int n = es;					\
	do {						\
		char c = *p1;				\
		*p1++ = *p2;				\
		*p2++ = c;				\
	} while (--n);					\
}

#define copy(i, j) { if (memtype == 0) *(long *)(i) = *(long *)(j);	\
		     else memcpy((i), (j), es); }

#define siftdown(l, u) {						\
	pu = (u) * es;							\
	copy(buf, a + (l)*es);						\
	for (pi = (l)*es; (pc = 2*pi) <= pu; pi = pc) {			\
		if (pc < pu && cmp(a+pc+es, a+pc) > 0) pc += es;	\
		copy(a + pi, a + pc);					\
	}								\
	copy(a + pi, buf);						\
	for (i = pi / es; (p = i/2) >= l; i = p) {			\
		if (cmp(a + p*es, a + i*es) > 0) break;			\
		swap(p, i);						\
	}								\
}

#define MYBUFSIZE 1024
void hsort5(char *a, int n, int es, int (*cmp)())
{
	int	j, i, c, p, u, memtype, pi, pu, pc;
	char	*buf, mybuf[MYBUFSIZE], *malloc();

	buf = mybuf;
	if (es > MYBUFSIZE && !(buf = malloc(es))) {
		qsort(a, n, es, cmp);
		return;
	}
	memtype = (a - (char*) 0) % sizeof(long)
		|| es!= sizeof(long);
	a -= es;
	for (j = n/2; j >= 1; j--)
		siftdown(j, n);
	for (j = n; j >= 2; j--) {
		swap(1, j);
		siftdown(1, j-1);
	}
	if (es > MYBUFSIZE)
		free(buf);
}