Caveat Emptor - the fact that google returns this page as one of the hits on median computation, does not mean this information is reliable. It is not! A better place to look would be somewhere else (I am too lazy to find the right reference, OK?).

Finding the Median in Linear Time

Let a₁, ..., a_n be n real numbers. We would like to compute their median in linear time. This can be done in linear time by a relatively complicated determinsitic algorithm (see any standard book on data-structures). Luckily, it can be also be done in linear time by the following simple algorithm:

FindKMedian( A, K )

Return the number in A which is the K-th in its size.

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 ).

Intuitively, the expected running time of this algorithm is linear because each recursive call takes on the average linear time, and each recursive call reduces the size of the problem by a constant factor.

Back to the linear programming applet