Question

Pseudocode and algorithm of finding median of unordered array in linear time.

Answer 1

This is a special case of a selection algorithm that can find the kth smallest element of an array with k is the half of the size of the array. There is an implementation that is linear in the worst case.

Generic selection algorithm

First let's see an algorithm find-kth that finds the kth smallest element of an array:

find-kth(A, k)
  pivot = random element of A
  (L, R) = split(A, pivot)
  if k = |L|+1, return pivot
  if k ≤ |L|  , return find-kth(L, k)
  if k > |L|+1, return find-kth(R, k-(|L|+1))

The function split(A, pivot) returns L,R such that all elements in R are greater than pivot and L all the others (minus one occurrence of pivot). Then all is done recursively.

This is O(n) in average but O(n²) in the worst case.

Linear worst case: the median-of-medians algorithm

A better pivot is the median of all the medians of sub arrays of A of size 5, by using calling the procedure on the array of these medians.

find-kth(A, k)
  B = [median(A[1], .., A[5]), median(A[6], .., A[10]), ..]
  pivot = find-kth(B, |B|/2)
  ...

This guarantees O(n) in all cases.