Editing Median (section)

==={{anchor|Ninther}} {{anchor|Remedian}} Efficient computation of the sample median===
Even though [[sorting algorithm|comparison-sorting]] ''n'' items requires {{math|[[Big O notation|Ω]](''n'' log ''n'')}} operations, [[selection algorithm]]s can compute the [[order statistic|{{mvar|k}}th-smallest of {{mvar|n}} items]] with only {{math|Θ(''n'')}} operations. This includes the median, which is the {{math|{{sfrac|''n''|2}}}}th order statistic (or for an even number of samples, the [[arithmetic mean]] of the two middle order statistics).<ref>{{cite book | isbn=0-201-00029-6 | author=Alfred V. Aho and John E. Hopcroft and Jeffrey D. Ullman | title=The Design and Analysis of Computer Algorithms | location=Reading/MA | publisher=Addison-Wesley | year=1974 | url-access=registration | url=https://archive.org/details/designanalysisof00ahoarich }} Here: Section 3.6 "Order Statistics", p.97-99, in particular Algorithm 3.6 and Theorem 3.9.</ref>

Selection algorithms still have the downside of requiring {{math|Ω(''n'')}} memory, that is, they need to have the full sample (or a linear-sized portion of it) in memory. Because this, as well as the linear time requirement, can be prohibitive, several estimation procedures for the median have been developed. A simple one is the median of three rule, which estimates the median as the median of a three-element subsample; this is commonly used as a subroutine in the [[quicksort]] sorting algorithm, which uses an estimate of its input's median. A more [[robust estimator]] is [[John Tukey|Tukey]]'s ''ninther'', which is the median of three rule applied with limited recursion:<ref>{{cite journal |first1=Jon L. |last1=Bentley |first2=M. Douglas |last2=McIlroy |title=Engineering a sort function |journal=Software: Practice and Experience |volume=23 |issue=11 |pages=1249–1265 |year=1993 |url=http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.8162 |doi=10.1002/spe.4380231105|s2cid=8822797 }}</ref> if {{mvar|A}} is the sample laid out as an [[array (data structure)|array]], and

{{block indent | em = 1.5 | text = {{math|1=med3(''A'') = med(''A''[1], ''A''[{{sfrac|''n''|2}}], ''A''[''n''])}},}}

then

{{block indent | em = 1.5 | text = {{math|1=ninther(''A'') = med3(med3(''A''[1 ... {{sfrac|1|3}}''n'']), med3(''A''[{{sfrac|1|3}}''n'' ... {{sfrac|2|3}}''n'']), med3(''A''[{{sfrac|2|3}}''n'' ... ''n'']))}}}}

The ''remedian'' is an estimator for the median that requires linear time but sub-linear memory, operating in a single pass over the sample.<ref>{{cite journal |last1=Rousseeuw |first1=Peter J. |last2=Bassett |first2=Gilbert W. Jr.|title=The remedian: a robust averaging method for large data sets |journal=J. Amer. Statist. Assoc. |volume=85 |issue=409 |year=1990 |url=http://wis.kuleuven.be/stat/robust/papers/publications-1990/rousseeuwbassett-remedian-jasa-1990.pdf |pages=97–104 |doi=10.1080/01621459.1990.10475311}}</ref>