[SciPy-dev] Sorting speed

[Travis Oliphant]

Francesc Altet wrote:

>Hi,
>
>It seems that scipy_core (0.9.0.1713) is far more slower than numarray
>(1.5.0) when sorting arrays:
>
>In [43]: t5=timeit.Timer('a=sc.empty(shape=10000);a.sort()', 'import 
>scipy.base as sc')
>
>In [44]: t5.repeat(3,100)
>Out[44]: [0.40603208541870117, 0.41605615615844727, 0.39800286293029785]
>
>In [45]: t4=timeit.Timer('a=na.array(None, shape=10000);a.sort()', 'import 
>numarray as na')
>
>In [46]: t4.repeat(3,100)
>Out[46]: [0.090479135513305664, 0.086208105087280273, 0.086167097091674805]
>
>i.e. numarray is roughly 5x faster than scipy_core.
>  
>
Scipy core is still using the old Numeric algorithm for sorting which 
uses the generic qsort function and the compare function pointer.  It 
looks like numarray is in-lining the sorting algorithm (and the argsort) 
for each data-type.   I suspect this could be the source of the 
impressive speed-up.  What do others think?    Also, numarray has at 
least three different sorting algorithms (quicksort, heapsort, and 
mergesort).  These could certainly be brought over fairly easily.   
Initially, I think I will try in-lining the quicksort algorithm for each 
data-type similar to numarray.

Thoughts?

-Travis