On 13 Okt, 18:33, Paul Rubin <http://phr...@NOSPAM.invalid> wrote: > 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. QuickSelect will find the median in O(log n) time.