August 20, 2010 Today’s exercise is about a relatively new
sorting algorithm. We start with an article Optimizing Your Wife
by Kevin Brown, which proposes that the best way for a man to
find a wife is to decide how many women he is willing to date
before he chooses a wife, we’ll call that N, determine which of
the first √N women is “best,” according to whatever matters to
him, and then choose the next woman after the first √N that is
better than any of the first √N women. For instance, to find the
marriageable woman in a batch of a hundred, date ten of them,
then marry the next one that is better than any of those ten.
You may not find the optimal woman, but you’ll be close. Eric
Burnett turned Brown’s idea into a sorting algorithm. First,
sample the first √N values at the beginning of an array, then
swap any of the remaining values that are better than the
greatest value of the sample to the end of the array, swap the
greatest value of the sample just before those at the end, then
recur on the smaller array