Deterministic selection
Deterministic selection is an algorithm for finding out the kth item in an unordered list of elements. As we have seen in the quickselect algorithm, we select a random “pivot” element that partitions the list into two sublists and calls itself recursively for one of the two sublists. In a deterministic selection algorithm, we choose a pivot element more efficiently instead of taking any random pivot element.
The main concept of the deterministic algorithm is to select a pivot element that produces a good split of the list, and a good split is one that divides the list into two halves. For instance, a good way to select a pivot element would be to choose the median of all the values. But we will need to sort the elements in order to find out the median element, which is not efficient, so instead, we try to find a way to select a pivot element that divides the list roughly in the middle.
The median of medians is a method that provides us...