Finding the median of medians of quicksort

Question

I am working on quick-sort with median of medians algorithm. I normally use the selection-sort to get the median of the subarrays of 5 elements. However, if there are thousands of subarrays, it means that I have to find a median of thousand medians. I think I cannot use the selection-sort to find that median because it is not optimal.

Question:

Can anyone suggest me a better way to find that median? Thanks in advance.

Answer 1

The median-of-medians algorithm doesn't work by finding the median of each block of size 5 and then running a sorting algorithm on them to find the median. Instead, you typically would sort each block, take the median of each, then recursively invoke the median-of-medians algorithm on these medians to get a good pivot. It's very uncommon to see the median-of-medians algorithm used in quicksort, since the constant factor in the O(n) runtime of the median-of-medians algorithm is so large that it tends to noticeably degrade performance.

There are several possible improvements you can try over this original approach. The simplest way to get a good pivot is just to pick a random element - this leads to Θ(n log n) runtime with very high probability. If you're not comfortable using randomness, you can try using the introselect algorithm, which is a modification of the median-of-medians algorithm that tries to lower the constant factor by guessing an element that might be a good pivot and cutting off the recursion early if one is found. You could also try writing introsort, which uses quicksort and switches to a different algorithm (usually heapsort) if it appears that the algorithm is degenerating.

Hope this helps!