On Thu, Oct 16, 2008 at 9:01 AM, Dan Weston
Google "median order statistic".
E.g. this is an interesting (and colorful) discussion:
http://ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/...
Hrmm, maths and statistics definitely aren't a strong area for me, but doesn't that PDF say on the second page that choosing i = 0 or i = n or i = median is equally naive? The rest of the document describes other interesting methods for getting the pivot. I couldn't follow the Wikipedia page on order statistics though. Still, with no assumptions as to the contents of a list whatsoever, when choosing 1 element to be the pivot, intuitively it makes no difference which one you choose. (Then again, I find statistical analysis rarely is intuitive.)