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. -- http://mail.python.org/mailman/listinfo/python-list
