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