non/spire — pull request #32 by tixxit (2012-10-17 04:08:21+00:00)
Title: Add fast selection algorithm to Spire.

This adds a fast, linear time selection algorithm to Spire. There are 2
flavours: Selection.quickSelect and Selection.linearSelect. The first is
analagous to quickSelect; in the general case it performs quite well,
but does not guarantee linear runtime and can perform poorly in some
instances. The second, linearSelect, guarantees linear time complexity,
at the cost of being 2-2.5x slower than quickSelect in the general case.