Paul Rubin <http://[EMAIL PROTECTED]> writes: > Tarjan discovered a guaranteed O(n) algorithm in the 1970's(?) whose > operation is much different and quite complex. But all of these need > more than one temp var. See an algorithms book like CLRS or Knuth > for more info.
Ehh, make that Blum, Floyd, Pratt, Rivest, and Tarjan, and the main different part is selecting the pivot, plus the complexity analysis. http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15451-f06/www/lectures/lect0907.pdf http://en.wikipedia.org/wiki/Selection_algorithm (see "median of medians algorithm") -- http://mail.python.org/mailman/listinfo/python-list