[adgjlsfhk1]

median of median does give you guarenteed n*log(n) but it doubles your memory reads per pass making it pretty poor. single random is almost guarenteed to take fewer passes (and median of 3-7 random values can make the number of extra passes over the minimum to be very low)

[SkiFire13]

You don't have to use median of medians for every pass, you can use it only when you detect that each pass is not making enough progress, i.e. when you hit the worst case.