medianOfMedians

[Andrei Alexandrescu via Digitalmars-d]

On 01/19/2016 09:26 PM, Timon Gehr wrote:
> 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.
[snip]

Thanks again for sharing your insight. FWIW there's a bit of variation 
floating on the Net regarding MoM. The Wikipedia article at 
https://en.wikipedia.org/wiki/Median_of_medians moves the medians of 
five to the beginning of the array (my implementation uses stride(), 
thus trading computation for data movement). I'm unclear on which 
approach is generally better.

http://austinrochford.com/posts/2013-10-28-median-of-medians.html does 
not mention the mutual recursion, suggesting (at least in a cursory 
reading) my wishy-washy previous implementation that doesn't use 
quickselect.

https://www.ics.uci.edu/~eppstein/161/960130.html only uses one 
recursive function, not two.

The original PICK algorithm at 
https://people.csail.mit.edu/rivest/pubs/BFPRT73.pdf only uses one 
recursive function.

Anyhow, I've implemented the two-functions version at 
https://github.com/D-Programming-Language/phobos/pull/3938. I'll next 
try whether the one-function version is just as good or better. Destroy?


Andrei