Newsgroups: sci.math
From: haoyuep@aol.com (Dan Hoey)
Date: Mar 14, 2000 8:45 PM
Subject: Re: Finding the median in 5 elements

Richard Sze wrote:
> Given a set of 5 elements, find the median of it in exactly 6
> comparisons

Look for the best of the best, and always reuse your leftovers.

First compare two pairs of elements, then compare the two maxima.
The maximum of four is too large to be the median. Discard it.
Of the remaining elements, one pair has already been compared.

Do it again (reusing the leftover compared pair).

Three elements remain; we want their maximum.  Discard the smaller
of the second leftover compared pair and return the larger of the
remaining two elements.

Dan Hoey                             posted and e-mailed
haoyuep@aol.com