[Numpy-discussion] A faster median (Wirth's method)

[Sturla Molden]

Sturla Molden skrev:
> We recently has a discussion regarding an optimization of NumPy's median 
> to average O(n) complexity. After some searching, I found out there is a 
> selection algorithm competitive in speed with Hoare's quick select.
>
> Reference:
> http://ndevilla.free.fr/median/median.pdf

After som more googling, I found this  text by Wirth himself:

http://www.oberon2005.ru/book/ads2004.pdf

The method is described on page 61 (57 in the PDF) as Hoare's quick 
select. So it seems it's just a less optimized version than that of 
Numerical Receipes, and the first reference (Devillard) was confused. 
Anyhow, it still has the advantage of looking nice in Cython and being 
very different from the Numerical Receipes code. We can rename 
wirthselect to quickselect then. Sorry for the confusion. I should have 
checked the source better.

Sturla Molden