One of these is randomized and runs in expected O(n) time.
The rest of this post shows my implementation.
Nice, but the worst case running time is
Ω(n2). It suffers from the same problem as Quicksort: picking a random pivot works well often enough to get a good expected running time, but if you're unlucky, it's really slow.
There is an algorithm to do it in garanteed linear time (although when done in Perl, the constants are so high that for most practical situations, one can better use sorting in C and picking the middle element).