  This paper describes a new median algorithm and a median approximation
algorithm. The former has O(n) average running time and the latter has O(n)
worst-case running time. These algorithms are highly competitive with the
standard algorithm when computing the median of a single data set, but are
significantly faster in updating the median when more data is added.
