Errata

I have a question about the implementation of the "median of three" method in the partition function for quicksort in this book (section 12.6 - Implementation and Analysis of Quicksort). It doesn't seem to follow from the explanation in the text.

In the text (paragraph 5 & 6 of Section 12.4 - Description of Quicksort) a randomized median of three method is described and makes sense to me. You pick 3 random values from the array to be sorted, choose their median value (by sorting those 3 elements and picking the middle one), and pivot around that. However, in the implementation, it looks like the median of the indices is being taken, rather than the median of the values at those indices. My understanding was that the aim would be to get the median of the values, and not the indices, in order to find a partition value that partitions the array as evenly as possible to get nlogn performance.

Here's a snippet with the relevant code

static int partition(void *data, int esize, int i, int k, int (*compare)(const void *key1, const void *key2)
char *a = data;
void *pval;
void *temp;
int r[3];

if ((pval = malloc(esize)) == NULL) {
return -1;
}
if ((temp = malloc(esize)) == NULL) {
free(pval);
return -1;
}

r[0] = (rand() % (k - i + 1)) + i;
r[1] = (rand() % (k - i + 1)) + i;
r[2] = (rand() % (k - i + 1)) + i;

issort(r, 3, sizeof(int), compare_int); // sorting indices instead of values..???
memcpy(pval, &a[r[1] * esize], esize);