Deterministic selection

The worst-case performance of a randomized selection algorithm is O(n²). It is possible to improve on a section of the randomized selection algorithm to obtain a worst-case performance of O(n). This kind of algorithm is called deterministic selection.

The general approach to the deterministic algorithm is listed here:

1. Select a pivot:
   1. Split a list of unordered items into groups of five elements each.
   2. Sort and find the median of all the groups.
   3. Repeat step 1 and step 2 recursively to obtain the true median of the list.
2. Use the true median to partition the list of unordered items.
3. Recurse into the part of the partitioned list that may contain the ith-smallest element.

Pivot selection

Previously, in the random selection algorithm, we selected the first element as the pivot. We shall replace that step with a sequence of steps that enables us to obtain the true or approximate median. This will improve the partitioning of the list about the pivot:

    def partition(unsorted_array...