Fast computation of the median by successive binning
arXiv:0806.3301
Abstract
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.
14 pages, 1 Postscript figure