[comp.theory] Finding Median of $n$, $n$ SMALL.

gasarch@brillig.cs.umd.edu (William Ian Gasarch) (10/11/90)

In KNUTH Vol. 3 (Page 215) he has a table for the BEST (in terms
or worse case) number of comparisons to find the $k$th largest
of $n$ numbers, where $1\le k \le n \le 10$.

Does anyone out there know if the table has been improved
or extended?  Or if anyone has worked out the best algorithm
for average case performance.

I am talking about VERY SMALL $n$, so the usual algorithms
may not suffice.

Please email responses to gasarch@cs.umd.edu

					bill