medianOfMedians

[Timon Gehr via Digitalmars-d]

On 01/20/2016 02:20 AM, Andrei Alexandrescu wrote:
> I've seldom have code write itself so beautifully. Which, of course,
> means it needs to be destroyed.
> https://github.com/D-Programming-Language/phobos/pull/3938 -- Andrei

This is not an implementation of the median of medians algorithm.

int[] bad(int n){
     if(n<=5){ return iota(n).array; }
     auto next=bad(n/5);
     return next.map!(a=>[a-2,a-1,a,a+n,a+n+1]).join;
}

void main(){
     import std.stdio;
     auto a=bad(5^^10);
     auto idx=medianOfMedians(a);
     double notLarger=a.count!(x=>x<=a[idx])/(1.0*a.length);
     writeln(notLarger); // 0.0100766
     assert(notLarger>=0.3); // fail
}

The real algorithm works by computing an /exact/ median of the medians 
and uses it as the pivot value for quickselect in order to compute the 
precise median of the full array. In the given implementation, the 
approximations accumulate with each recursive invocation and no constant 
guarantees can be given on the percentile of the result.