Incremental median

For some reason, I was thinking about averages and how it's possible to calculate a mean incrementally as data comes in. My mind then wandered and wondered if it's possible to calculate the median incrementally too.

My initial thoughts were no, and then I hesitated and wondered if it was possible by storing some sort of interval, but then I realised that wouldn't work either. So I resorted to Google, and Stack Overflow in particular.

The answer looks like a 'no' if you want the genuine median. However if you are happy with a reasonable approximation, the answer is more like a 'yes'.

So that's good to know!

[Image credit: Janne]

P.S. Flickr searches for 'median' really do bring up the most incredible variety of photos!