Code

This is an implementation of linear time selection by Blum, Floyd, Pratt, Rivest, and Tarjon in Java.

Pseudocode:

BSelect(A,k):
    If |A| == 1 return A[1]
    p = GoodPivot(A)
    S = { A[i] | A[i] < p }
    L = { A[i] | A[i] > p }
    If |S| >= k return BSelect(S,k)
    else if |S| == k-1 return p
    else return BSelect(L, k-|S|-1)

GoodPivot(A):
    Divide A into n/5 groups of 5 elements each
    Find the median of each group
    Use BSelect to find the median, p, of the n/5 medians
    Return p

View implementation