numpy/numpy — pull request #3360 by juliantaylor (2013-05-23 22:09:34+00:00)
Title:  add quickselect algorithm and expose it via partition

As announced on the list (http://mail.scipy.org/pipermail/numpy-discussion/2013-May/066645.html) here my quickselect based partition code.
This pull request should be considered as work in progress, but I want to get some feedback on it before I clean it up.

A partition sorts the kth element into its sorted order and moves all
smaller elements before the kth element and all larger elements behind it.
The ordering of all elements in the partitions is undefined.

It is implemented via the quickselect algorithm which has average linear
complexity compared to a full sort that has linearithmic complexity.
The worst case is quadratic.

String selection is implemented in terms of quicksort which has the same
properties as a selection for now.

As first method median is implemented as a partition now.
Another method I'm aware of that profits is percentile.

The naming of "partition" might confuse C++ users, in C++ its called nth_element but I think partition is a good name, the C++ variant of partition (partition by a comparison function) would probably be slower than simply sorting the array.

Right now it only has one algorithm.
I think a worst case linear but much slower variant can be implemented by choosing the quickselect pivot via a median of medians algorithm, but I'm not sure about that and also doubtful if its worth implementing (you can always heap/merge sort to get O(nlog(n)) worst case)