/*
 * modified version to use a random pivot.  BUGGY
 *
 * an implemention of quicksort.  bsy@cs.ucsd.edu, 02/06/2002.
 *
 * because of the poor choice of pivot -- the first element of the
 * array -- this algorithm has worse case running time of O(n^2).
 * with random input, the expected running time is O(n log(n)).
 *
 * preconditions:
 *
 * array is an array of nelt integers.  0 <= nelt <= INT_MAX
 *
 * postconditions:
 *
 * let array' denote the array after the algorithm terminates
 *
 * forall i: 0 <= i < nelt-1 --> array'[i] <= array'[i+1]
 *
 * exists phi: phi a permutation on {0... nelt-1} and
 *  forall i: 0 <= i < nelt --> array'[phi(i)] = array[i]
 *
 * a permutation on the set S={0... nelt-1} is a function that is a
 * bijection S->S.
 */
void sort(int	*array,
	  int	nelt)
{
	int	smallix, bigix, mid, t;

	/*
	 * base case: array of zero or one element is sorted by definition.
	 * the permutation is the identity permutation.
	 */
	if (nelt < 2) return;
	smallix = 0; bigix = nelt;
	/*
	 * XXX chose a better pivot!  by using a random pivot, with
	 * high probability we will avoid the O(n^2) performance
	 * quagmire.
	 */
	mid = array[random() % nelt];
	while (smallix < bigix) {
		/*
		 * loop invariants:
		 *
		 * smallix <= nelt; 0 <= bigix.
		 *
		 * forall i: 0 <= i < smallix --> array[i] <= mid
		 *
		 * forall i: bigix <= i < nelt --> mid < array[i]
		 */
		while (smallix < nelt && array[smallix] <= mid)
			smallix++;
		while (0 < bigix && mid < array[bigix-1])
			bigix--;
		if (!(smallix == nelt || 0 == bigix || smallix == bigix)) {
			/* permutation */
			t = array[smallix];
			array[smallix] = array[bigix - 1];
			array[bigix - 1] = t;
		}
	}
	/* smallix == bigix; 1 <= smallix */
	t = array[smallix-1]; array[smallix-1] = array[0]; array[0] = t;
	/*
	 * problem size shrinks:
	 *
	 * smallix <= nelt --> smallix-1 < nelt
	 */
	sort(array,smallix-1);
	/*
	 * problem size shrinks:
	 *
	 * 1 <= smallix --> nelt-smallix < nelt.
	 */
	sort(array+smallix,nelt-smallix);
	/*
	 * elements are renamed (subarray offsets), and permutations
	 * require some touchup before function composition.
	 */
}