Finding the Median in Linear Time

Pick randomly a number a from A = {a₁, ..., a_n}.

Partition the n numbers into two sets:

• S - all the numbers smaller than a
• B - all the numbers bigger than a

If |S| = K-1 then a is the required K-median. Return a

If |S| < K-1 then the K-median lies somewhere in B. Call recursively to FindKMedian( B, K - |S| - 1 )

Else, call recursively to FindKMedian( S, K ).

Read full article from Finding the Median in Linear Time