We will look at two approaches. We start with expected $O(n)$ time and then try to achieve worst-case $O(n)$ time.

The problem a median-finding algorithm solves is the following:

Given an array $A=[1,...,n]$ of $n$ numbers and an index $i$, where $1≤i≤n$, find the $ith$ smallest element of $A$.

This problem can certainly be solved using a sorting algorithm to sort a list of numbers and return the value at the $i^{th}$ index. However, many sorting algorithms can’t go faster than $n \log n$ **time. A median-finding algorithm can find the $i^{th}$ smallest element in a list in $O(n)$ time.

Quickselect

This algorithm uses partitioning but in a different way from quicksort.

It is still a recursive algorithm but it has fewer recursive calls than quicksort. Here is how it works:

Unlike quicksort where you recurse on both sides, you only recurse on one side. In the best case, this makes the recurrence $T(n) = T(n/2) + O(n)$, which solves to $O(n)$.

The recursion tree can be seen as a geometric series which we can sum.

Note that this assumes that we are lucky and partition roughly in half. In reality, the size of the partition depends on the pivot element so the overall efficiency of the algorithm depends on how we choose the pivot element.

The Median-of-medians Algorithm

The median-of-medians algorithm is a deterministic linear-time selection algorithm.

The algorithm works by:

  1. Divide a list into sublists and then determine the approximate median in each of the sublists.
  2. Take those medians and puts them into a list and finds the median of that list. We use that median value as a pivot and compares other elements of the list against the pivot.
  3. If an element is less than the pivot value, the element is placed to the left of the pivot, and if the element has a value greater than the pivot, it is placed to the right.
  4. The algorithm recurses on the list, honing in on the value it is looking for.