The Quick Mom Algorithm

[Ivan Kazmenko via Digitalmars-d]

On Friday, 29 January 2016 at 22:47:44 UTC, Andrei Alexandrescu 
wrote:
> http://dpaste.dzfl.pl/05a82699acc8
>
> While thinking of MoM and the core reasons of its being slow 
> (adds nice structure to its input and then "forgets" most of it 
> when recursing), I stumbled upon a different algorithm. It's 
> much simpler, also deterministic and faster than MoM for many 
> (most?) inputs. But it's not guaranteed to be linear. After 
> having pounded at this for many hours, it is clear that I am in 
> need of some serious due destruction. I call it a "quick median 
> of medians" or in short "quick mom".

The code does not compile when I try to use topN, as medianOfUpTo 
is not present.  Please include it.

Anyway, for now, I just wanted to quickly check whether my 
previous attack on topN would have any effect here.

I've replaced the line
     if (r.length <= 5) return medianOfUpTo!(5, lp)(r);
with a quick fix:
     if (r.length == 2)
     {
         if (!less (r.front, r.back)) swap (r.front, r.back);
         return 0;
     }
     if (r.length == 1) return 0;

Here is the code (just glued together the two snippets):
http://dpaste.dzfl.pl/f648a600a11d

Turns out like maybe it does have its effect (size = 5 million):

building Element array: 2442 msecs
checking Element array: 2432 msecs
checking int array: 388 msecs
checking random int array: 140 msecs
checking increasing int array: 41 msecs
checking decreasing int array: 42 msecs

The int array built by the attack makes the program run slower 
than a random array, and the ratio increases with size.