Sorting troubles

[Steven D'Aprano]

On Mon, 14 May 2007 21:45:26 -0700, seyensubs wrote:

> Ah, I see, just slicing it like that.. nice! But after doing some timing
> tests, the version that's in place and using partitions is about twice
> faster than the non hybrid qSort. The hybrid one, with insertionsSort
> used for smaller lists works faster, but in a weird way. When given
> lists of 2000, the best bet to is to set the threshold to 14, but when
> given a list of 40000, 14 is slow, but a threshold of 200(less or more
> is slower, again) makes it about 8 times faster than a normal qSort, and
> 4 times faster than an in-place qSort, using a self -defined
> partitioning alg.
> 
> Making a hybrid out of the in-place partitioned qSort makes it a bit
> faster, but not by much compared to the other hybrid which uses list
> comprehensions.
> 
> Teach said that the optimal threshold in hybrids is 14-16, but guess he
> wasn't so right after all =\\ The overhead of using insertion sort on a
> longer list turns out to be faster than just piling on recursions, when
> confronted with bigger lists.

Teach may have been thinking of languages where comparing items is fast 
and moving data is slow; Python is the opposite, comparisons invoke a 
whole bucket-full of object-oriented mechanism, while moving data just 
means moving pointers.

It needs to be said, just in case... this is a good learning exercise, 
but don't use this in real code. You aren't going to get within a bull's 
roar of the performance of the built-in sort method. Tim Peter's 
"timsort" is amazingly powerful; you can read about it here:

http://pythonowns.blogspot.com/2002_07_28_pythonowns_archive.html#79780508

http://svn.python.org/projects/python/trunk/Objects/listsort.txt



-- 
Steven.