efficient running median

[Paul Rubin]

Janto Dreijer <jantod at gmail.com> writes:
> I'm looking for code that will calculate the running median of a
> sequence, efficiently. (I'm trying to subtract the running median from
> a signal to correct for gradual drift).

Is that a known and valid technique of correcting for drift?  Maybe
what you really want is a high-pass filter, to remove very low
frequency components (drift) from the signal.  You can do that with
standard digital filters.  Using something depending on ordering
within the samples (i.e. the median) seems weird to me, but I'm no
expert.

The obvious way to compute a running median involves a tree structure
so you can quickly insert and delete elements, and find the median.
That would be asymtotically O(n log n) but messy to implement.