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.