I really like the randomization solution. Worst case? What worst case?
EDIT: I wrote worst case #permutations. That's the best case #comparisons. So, no, I don't mean a sorted sequence ;)
A much more interesting case is the median-of-three pivot. (Namely, median of first / middle / last elements). You can still do it, however.
I feel like the recursive median of medians throws away a great deal of information, given all the comparisons you make. At the very least, for the final step, you know where the high and low values go, and could easily place them in the appropriate sides of the array.
