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

Robert Kern robert.kern@gmail....
Thu May 7 12:46:37 CDT 2009


On Thu, May 7, 2009 at 12:46, Aahz <aahz@pythoncraft.com> wrote:
> 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).

We actually have a few sorting algorithms, including a stable mergesort:

  http://docs.scipy.org/doc/numpy/reference/generated/numpy.sort.html

The last time we looked at this, we decided that implementing timsort
probably wouldn't be much better than mergesort. timsort is designed
for the case of expensive compare operations, and we have relatively
cheap compares.

Happy to be proven wrong, of course.

-- 
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless
enigma that is made terrible by our own mad attempt to interpret it as
though it had an underlying truth."
  -- Umberto Eco


More information about the Scipy-dev mailing list