/************************************************
*						*
* qsort.c					*
*						*
* Unix-style general purpose quicksort		*
*						*
************************************************/

/* REVISION HISTORY

07/18/84  CEM  create file

*/


#define ERROR -1
#define NULL 0
#define OK 0


/* private functions */

static quick(), swap();


/* non-local variables */

static int size, (*comp)();


qsort(base,count,sz,cmp)
char *base;
int count, sz;
int (*cmp)();
{
	static char *end;

	comp = cmp;
	end = base + (count - 1) * (size = sz);
	quick(base,end);
}


static quick(lo,hi)
char *lo, *hi;
{
	char *i, *j, *pivot;

	if ( lo <  hi) {
		i = lo;
		j = pivot = hi;
loop:
			while (i < j && (*comp)(i,pivot) <= 0)
				i += size;
			while (j > i && (*comp)(j,pivot) >= 0)
				j -= size;
			if (i < j) {
				swap(i,j);
				goto loop;
			}

		swap(i,hi);

		/* to minimize stack depth do smaller partition first */

		if (i - lo < hi - i) {
			quick(lo,i - size);
			quick(i + size,hi);
		}
		else {
			quick(i + size,hi);
			quick(lo,i - size);
		}
	}
}


static swap(a,b)
char *a, *b;
{
	static int ch, nchars;

	nchars = size;
	while (--nchars >= 0) {
		ch = *a;
		*a++ = *b;
		*b++ = ch;
	}
}