On: Advice to a Beginning Graduate Student - Manuel Blum (CMU)

[yters]

Did not realize this: "the median of n integers can be found with just O(n) comparisons."

Must figure this out!

[sparky → yters]

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 ). The constant factor is non-trivial here (<= 24n comparisons for this one) but for large datasets it will eventually be faster than sorting.