[computer-go] OT: median of a data stream

[John Tromp]

On 8/16/07, Darren Cook <darren at dcook.org> wrote:
> Apologies for the off-topic post, but I know lots of people here are
> interested in statistics and algorithms.
>
> Calculating the mean of a stream of numbers [1] is easy: just keep track
> of the sum and the count, and divide at the end. But what about the
> median? I think I always need to buffer at least half the numbers, but
> does anyone know for sure, or know a clever algorithm [2]?

You'll have to remember all numbers.
If you've seen a_0 < a_1 < a_2 < ... < a_n   so far,
then for any i, 0<=i<=n, you'll have to ouput a_i after an additional
(n-i) values less than a_0, and i values greater than a_n.

regards,
-John