From my understanding, the medians of medians algorithm calls quickselect recursively. What i'm having trouble understanding is what median of medians should return. The idea is that it returns a good pivot value, but to perform quickselect we need a pivot index not a pivot value. Is there gap in my understanding? I've looked at online resources and still dont get it.

CodePudding user response：

Your understanding is flawed.

Quickselect (and quicksort) start with a pivot value, not a pivot index. The partition function returns a pivot index, which is where the pivot value ended up after the partition. There's no way to predict where that will be.

Median-of-medians finds a pivot value guaranteed to be not too far from the middle, which is enough to guarantee linear time complexity (for quickselect).

It's really only of theoretical interest. Selecting the pivot at random is much faster, which more than compensates for the occasional bad pivot selection.