Sorting troubles

[Aether.Singularity at gmail.com]

On May 15, 11:54 am, Steven D'Aprano
<ste... at REMOVE.THIS.cybersource.com.au> wrote:
> 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#797...
>
> http://svn.python.org/projects/python/trunk/Objects/listsort.txt
>
> --
> Steven.

Yeah, I know any stuff your average CS student will crank out is way
below anything in-built in the core language and libraries. After all,
smart, experienced people worked on those a lot more than me on
these :)

The blog post is dead, but the .txt is alive(it's the svn of
python.org, after all). Gonna read it but looks a bit beyond my level
of comprehension, for now anyway.

Thanks for all the answers! ..oh, got a 10(out of 10) points in class
for the program. Writing stuff in a language no one else learns at the
university and doing 5 versions of quickSort to test performance
must've paid off. Thanks again :)