Re: Median: Oasis and Fast Sorting Algorithm

["Morten Welinder" <mwelinder gmail com>]

The finding on the k-largest element in an unordered sequence of n elements is
a linear-time and (if memory serves) constant-space problem in terms of n.

See Knuth for details.

The trouble with the algorithm is that it is rather complicated.  More
code means
more chances of bugs.  Unless you are Knuth, of course.

Add to that that there are several different "medians" out there -- I
think we have
no less than three in Gnumeric -- out there and sorting starts to look
appealing.

Morten