Fast Computation of the Median by Successive Binning (stat.cmu.edu)

Needs a [2008], and there has been further progress on this subject subsequently, for example: https://doi.org/10.1109/TCSVT.2014.2376137