[SciPy-dev] fast sorting of most numpy array types

Aahz aahz@pythoncraft....
Thu May 7 11:46:20 CDT 2009


On Thu, May 07, 2009, Andrew Schein wrote:
> 
> I have recently release highly optimized type-specific C routines for
> sorting arrays of numeric types:
> **http://bitbucket.org/ais/usort/wiki/Home
> 
> The code was motivated in part by noting that the numpy implementation of
> sort appears to be a template-ized (over comparison) quicksort... and radix
> sort is often the better choice.  Actually, it has been a few months since I
> looked at the numpy source, so don't quote me.  The usort routines use a
> variety of strategies depending on the size of the array: radix sort, quick
> sort, insertion sort.

Speaking as someone who doesn't know anything about NumPy, have you
looked at the timsort used in Python itself?  One of the advantages of
timsort is that it's guaranteed to be stable (elements that compare equal
retain their relative ordering from before sorting).
-- 
Aahz (aahz@pythoncraft.com)           <*>         http://www.pythoncraft.com/

"It is easier to optimize correct code than to correct optimized code."
--Bill Harlan


More information about the Scipy-dev mailing list