What are the advantages and disadvantages of median-of-medians algorithm?

1 Median-of-medians algorithm

The median-of-medians algorithm is a recursive method to find the median of a set of numbers in linear time. The median is the middle element of a sorted array, or the average of the two middle elements if the array has an even length. To use this algorithm, divide the array into groups of five elements each, and sort each group. Find the median of each group, and put them in a new array. Recursively apply the median-of-medians algorithm to the new array until you find the median of medians. Then use this median as the pivot for quicksort.

2 Advantages of median-of-medians algorithm

The main advantage of using the median-of-medians algorithm as the pivot selection method for quicksort is that it guarantees a good balance of the partitions, regardless of the order of the original array. This means that the quicksort algorithm will always run in O(n log n) time, where n is the size of the array. This is better than the worst-case scenario of O(n^2) time for randomized quicksort, which can happen if the array is already sorted or reverse-sorted. Another advantage of median-of-medians algorithm is that it is deterministic, meaning that it will always produce the same result for the same input, unlike randomized quicksort, which can vary depending on the random choices.

3 Disadvantages of median-of-medians algorithm

However, the median-of-medians algorithm also has some drawbacks that limit its practical use. One disadvantage is that it is more complex and harder to implement than randomized quicksort, which only requires a simple random number generator. Another disadvantage is that it has a high constant factor in its running time, meaning that it is slower than randomized quicksort for small or moderate-sized arrays. This is because it involves sorting groups of five elements, creating a new array of medians, and recursively calling itself multiple times, which adds a lot of overhead. Moreover, the median-of-medians algorithm does not take advantage of any existing order or structure in the array, unlike some other pivot selection methods, such as using the first, last, or middle element, or using the median of three random elements.

4 When to use median-of-medians algorithm

Given these advantages and disadvantages, when should you use the median-of-medians algorithm as the pivot selection method for quicksort? The answer depends on your specific situation and requirements. If you need a guaranteed worst-case performance of O(n log n) time, and you are dealing with large or unknown-sized arrays, then the median-of-medians algorithm might be a good choice. However, if you are more concerned about the average-case performance, and you are working with small or moderate-sized arrays, or arrays that have some order or structure, then randomized quicksort might be faster and simpler. In any case, you should always test and compare different algorithms on your data and environment, and choose the one that suits your needs best.

5 Here’s what else to consider

This is a space to share examples, stories, or insights that don’t fit into any of the previous sections. What else would you like to add?