[SciPy-dev] Sorting speed

[Travis Oliphant]

Fernando Perez wrote:

>Travis Oliphant wrote:
>
>  
>
>>There are many sorting algorithms in numarray.  I'm not sure which one 
>>is being used regularly, but I'd like to see them brought over, though, 
>>which shouldn't be too big of a deal and is on the radar.  
>>    
>>
>
>It may be worth noting that the sort code in python's core, for 
>somelist.sort(), is to my understanding, state of the art.  Tim Peters a while 
>ago (py2.2, I think) brought the full weight of his considerable algorithmic 
>talent to bear on this problem, as well as some recent academic results.  I 
>don't know how this compares to what numarray uses, but it may be worth 
>investigating/copying.
>
>If Tim's work is as good as it is claimed to be (and I have much respect for 
>his claims), it might be a good idea to use a stripped version of his code 
>which doesn't have to deal with the generalities of python lists (and all the 
>per-item typechecking needed there).
>
>  
>
Thanks for the suggestions.  This sounds good.  The only possible 
drawback is that timsort (as he calls it --- a modified mergesort) 
requires temporary storage on the order of N//2 * 
sizeof(basic_element).   So, I could see it being a choice to consider 
when more sorting algorithms are added.  

It's also more complicated to grab his sorting algorithm then the nicely 
laid out numarray versions :-)

Definitely something to think about.  Anybody want a fun project :-)

-Travis