CSE 127 -- Introduction to Computer Security

An example find-the-error proof-of-correctness question: What is wrong with the following code? (Assume that the median_to_front implementation is correct.)

#define	SSWAP(x,n)	do {if (x[n] > x[n+1]) SWAP(x,n);} while(0)
/* 0 <= nelt < INT_MAX, base[0..nelt-1] valid */
void	quicksort(int	*base,
		  int	nelt)
{
	int pivot, t, hi, lo;

	switch (nelt) { /* base cases */
	case 2: SSWAP(base,0); /* fall through */
	case 0: case 1: return;
	}
	median_to_front(base, nelt); pivot = base[0];
	lo = 1; hi = nelt-1;
	/* base[1..lo-1] <= pivot < base[hi+1,nelt-1] */
	while (lo <= hi) {
		while (lo < nelt && base[lo] <= pivot)
			lo++;
		while (0 <= hi && pivot < base[hi])
			--hi;
		t = base[lo]; base[lo] = base[hi]; base[hi] = t;
	}
	while (0 <= hi && base[hi] == pivot)
		hi--;
	if (0 < hi) quicksort(base,hi+1);
	if (lo < nelt)
		quicksort(base+lo,nelt-lo);
}