#include <stddef.h>

extern	char	*memcpy();

char	*_qbuf = NULL;		/* pointer to storage for qsort() */

#define	PIVOT			((i+j)>>1)
#define moveitem(dst,src,size)	if(dst != src) memcpy(dst, src, size)

static _wqsort(base, lo, hi, cmp)
	register int *base;
	register int lo;
	register int hi;
	register int (*cmp)();
	{
	int k;
	register int i, j, t;
	register int *p = &k;

	while(hi > lo)
		{
		i = lo;
		j = hi;
		t = PIVOT;
		*p = base[t];
		base[t] = base[i];
		base[i] = *p;
		while(i < j)
			{
			while(((*cmp)((base+j), p)) > 0)
				--j;
			base[i] = base[j];
			while((i < j) && (((*cmp)((base+i), p)) <= 0))
				++i;
			base[j] = base[i];
			}
		base[i] = *p;
		if((i - lo) < (hi - i))
			{
			_wqsort(base, lo, (i - 1), cmp);
			lo = i + 1;
			}
		else
			{
			_wqsort(base, (i + 1), hi, cmp);
			hi = i - 1;
			}
		}
	}

static _lqsort(base, lo, hi, cmp)
	register long *base;
	register int lo;
	register int hi;
	register int (*cmp)();
	{
	long k;
	register int i, j, t;
	register long *p = &k;

	while(hi > lo)
		{
		i = lo;
		j = hi;
		t = PIVOT;
		*p = base[t];
		base[t] = base[i];
		base[i] = *p;
		while(i < j)
			{
			while(((*cmp)((base+j), p)) > 0)
				--j;
			base[i] = base[j];
			while((i < j) && (((*cmp)((base+i), p)) <= 0))
				++i;
			base[j] = base[i];
			}
		base[i] = *p;
		if((i - lo) < (hi - i))
			{
			_lqsort(base, lo, (i - 1), cmp);
			lo = i + 1;
			}
		else
			{
			_lqsort(base, (i + 1), hi, cmp);
			hi = i - 1;
			}
		}
	}

static _nqsort(base, lo, hi, size, cmp)
	register char *base;
	register int lo;
	register int hi;
	register int size;
	register int (*cmp)();
	{
	register int i, j;
	register char *p = _qbuf;

	while(hi > lo)
		{
		i = lo;
		j = hi;
		p = (base+size*PIVOT);
		moveitem(_qbuf, p, size);
		moveitem(p, (base+size*i), size);
		moveitem((base+size*i), _qbuf, size);
		p = _qbuf;
		while(i < j)
			{
			while(((*cmp)((base+size*j), p)) > 0)
				--j;
			moveitem((base+size*i), (base+size*j), size);
			while((i < j) && (((*cmp)((base+size*i), p)) <= 0))
				++i;
			moveitem((base+size*j), (base+size*i), size);
			}
		moveitem((base+size*i), p, size);
		if((i - lo) < (hi - i))
			{
			_nqsort(base, lo, (i - 1), size, cmp);
			lo = i + 1;
			}
		else
			{
			_nqsort(base, (i + 1), hi, size, cmp);
			hi = i - 1;
			}
		}
	}

qsort(base, num, size, cmp)
	char *base;
	int num;
	int size;
	int (*cmp)();
	{
	char _qtemp[128];

	if(_qbuf == NULL)
		{
		if(size > sizeof(_qtemp))	/* records too large! */
			return;
		_qbuf = _qtemp;
		}
	if(size == 2)
		_wqsort(base, 0, num-1, cmp);
	else if(size == 4)
		_lqsort(base, 0, num-1, cmp);
	else
		_nqsort(base, 0, num-1, size, cmp);
	if(_qbuf == _qtemp)
		_qbuf = NULL;
	}