There are a couple linear-time selection algorithms, some randomized and some not. An example of the latter is described here ( http://www.ics.uci.edu/~eppstei

There are a couple linear-time selection algorithms, some randomized and some not. An example of the latter is described here ( http://www.ics.uci.edu/~eppstein/161/960130.html http://www.ics.uci.edu/~eppstein/161/960130.html ). The constant factor is non-trivial here (<= 24n comparisons for this one) but for large datasets it will eventually be faster than sorting.