Selection

In computer science it is often desirable to return the i-th smallest element. This obviously can be done with sorting the items and returning the i-th element in the sorted list; however, if the list requires a comparison based sort algorithm, we would need a better way to accomplish this in linear time.

The procedure select, returns the i-th smallest element in linear time, O(n).
  1. Divide the n elements of the input array into partitions of 5 elements, which would yield ⌊n/5⌋ partitions of 5 elements and at most one partition of the remaining n mod 5 elements.
  2. Find the median of each partition by sorting each, utilizing Insertion sort.
  3. Use Select recursively on these medians to find the median-of-medians.
  4. Partition the input around the median-of-medians using a modified version of partition subroutine of Quicksort that would take the pivot as an input.
  5. If i = median-of-medians then return the median-of-medians.Otherwise, use Select recursively using the low side if i < median-of-medians, otherwise the high side.