text: /*
   * qsort.c
   *	Qsort algorithm
   *
   * Based on technology:
   * Copyright (c) 1980, 1983 The Regents of the University of California.
   * All rights reserved.
   *
   * Our own version of the system qsort routine which is faster by an
   * average of 25%, with lows and highs of 10% and 50%.
   *
   * The THRESHold below is the insertion sort threshold, and has been
   * adjusted for records of size 48 bytes.  The MTHREShold is where we
   * stop finding a better median.
   */
  #define	THRESH 4		/* threshold for insertion */
  #define	MTHRESH	6		/* threshold for median */
  
  static int (*qcmp)();		/* the comparison routine */
  static int qsz;			/* size of each record */
  static int thresh;		/* THRESHold in chars */
  static int mthresh;		/* MTHRESHold in chars */
  
  static int qst();
  
  /*
   * qsort()
   *
   * First, set up some global parameters for qst to share.  Then, quicksort
   * with qst(), and then a cleanup insertion sort ourselves.  Sound simple?
   * It's not...
   */
  void
  qsort(void *base, int n, unsigned int size, int (*compar)(void *, void *))
  {
  	register char c, *i, *j, *lo, *hi;
  	char *min, *max;
  
  	if (n <= 1) {
  		return;
  	}
  	qsz = size;
  	qcmp = compar;
  	thresh = qsz * THRESH;
  	mthresh = qsz * MTHRESH;
  	max = base + n * qsz;
  	if (n >= THRESH) {
  		qst(base, max);
  		hi = base + thresh;
  	} else {
  		hi = max;
  	}
  	/*
  	 * First put smallest element, which must be in the first THRESH, in
  	 * the first position as a sentinel.  This is done just by searching
  	 * the first THRESH elements (or the first n if n < THRESH), finding
  	 * the min, and swapping it into the first position.
  	 */
  	for (j = lo = base; (lo += qsz) < hi;) {
  		if (qcmp(j, lo) > 0) {
  			j = lo;
  		}
  	}
  	if (j != base) {
  		/* swap j into place */
  		for (i = base, hi = base + qsz; i < hi; ) {
  			c = *j;
  			*j++ = *i;
  			*i++ = c;
  		}
  	}
  	/*
  	 * With our sentinel in place, we now run the following hyper-fast
  	 * insertion sort.  For each remaining element, min, from [1] to [n-1],
  	 * set hi to the index of the element AFTER which this one goes.
  	 * Then, do the standard insertion sort shift on a character at a time
  	 * basis for each element in the frob.
  	 */
  	for (min = base; (hi = min += qsz) < max; ) {
  		while (qcmp(hi -= qsz, min) > 0)
  			/* void */;
  		if ((hi += qsz) != min) {
  			for (lo = min + qsz; --lo >= min; ) {
  				c = *lo;
  				for (i = j = lo; (j -= qsz) >= hi; i = j) {
  					*i = *j;
  				}
  				*i = c;
  			}
  		}
  	}
  }
  
  /*
   * qst()
   *
   * Do a quicksort
   * First, find the median element, and put that one in the first place as the
   * discriminator.  (This "median" is just the median of the first, last and
   * middle elements).  (Using this median instead of the first element is a big
   * win).  Then, the usual partitioning/swapping, followed by moving the
   * discriminator into the right place.  Then, figure out the sizes of the two
   * partions, do the smaller one recursively and the larger one via a repeat of
   * this code.  Stopping when there are less than THRESH elements in a partition
   * and cleaning up with an insertion sort (in our caller) is a huge win.
   * All data swaps are done in-line, which is space-losing but time-saving.
   * (And there are only three places where this is done).
   */
  static int
  qst(char *base, char *max)
  {
  	register char c, *i, *j, *jj;
  	register int ii;
  	char *mid, *tmp;
  	int lo, hi;
  
  	/*
  	 * At the top here, lo is the number of characters of elements in the
  	 * current partition.  (Which should be max - base).
  	 * Find the median of the first, last, and middle element and make
  	 * that the middle element.  Set j to largest of first and middle.
  	 * If max is larger than that guy, then it's that guy, else compare
  	 * max with loser of first and take larger.  Things are set up to
  	 * prefer the middle, then the first in case of ties.
  	 */
  	lo = max - base;		/* number of elements as chars */
  	do	{
  		mid = i = base + qsz * ((lo / qsz) >> 1);
  		if (lo >= mthresh) {
  			j = (qcmp((jj = base), i) > 0 ? jj : i);
  			if (qcmp(j, (tmp = max - qsz)) > 0) {
  				/* switch to first loser */
  				j = (j == jj ? i : jj);
  				if (qcmp(j, tmp) < 0) {
  					j = tmp;
  				}
  			}
  			if (j != i) {
  				ii = qsz;
  				do	{
  					c = *i;
  					*i++ = *j;
  					*j++ = c;
  				} while (--ii);
  			}
  		}
  		/*
  		 * Semi-standard quicksort partitioning/swapping
  		 */
  		for (i = base, j = max - qsz; ; ) {
  			while (i < mid && qcmp(i, mid) <= 0) {
  				i += qsz;
  			}
  			while (j > mid) {
  				if (qcmp(mid, j) <= 0) {
  					j -= qsz;
  					continue;
  				}
  				tmp = i + qsz;	/* value of i after swap */
  				if (i == mid) {
  					/* j <-> mid, new mid is j */
  					mid = jj = j;
  				} else {
  					/* i <-> j */
  					jj = j;
  					j -= qsz;
  				}
  				goto swap;
  			}
  			if (i == mid) {
  				break;
  			} else {
  				/* i <-> mid, new mid is i */
  				jj = mid;
  				tmp = mid = i;	/* value of i after swap */
  				j -= qsz;
  			}
  		swap:
  			ii = qsz;
  			do	{
  				c = *i;
  				*i++ = *jj;
  				*jj++ = c;
  			} while (--ii);
  			i = tmp;
  		}
  		/*
  		 * Look at sizes of the two partitions, do the smaller
  		 * one first by recursion, then do the larger one by
  		 * making sure lo is its size, base and max are update
  		 * correctly, and branching back.  But only repeat
  		 * (recursively or by branching) if the partition is
  		 * of at least size THRESH.
  		 */
  		i = (j = mid) + qsz;
  		if ((lo = j - base) <= (hi = max - i)) {
  			if (lo >= thresh) {
  				qst(base, j);
  			}
  			base = i;
  			lo = hi;
  		} else {
  			if (hi >= thresh) {
  				qst(i, max);
  			}
  			max = j;
  		}
  	} while (lo >= thresh);
  }
  