python 3's adoption
Steven D'Aprano
steven at REMOVE.THIS.cybersource.com.au
Thu Jan 28 02:56:00 CET 2010
On Wed, 27 Jan 2010 16:44:18 -0800, Carl Banks wrote:
>> You're referring to the O(N**2) bit, right? I am sure he knew it was O
>> (N*log(N)), which is still worse than O(N) for key.
>>
>> If he didn't, well, Python has some fundamental flaws in its basic sort
>> algorithm.
>
> Quicksort is O(N**2) worst case, perhaps that's what he meant.
No, apparently I was delusional.
> I'm not
> sure about timsort but since it's based on quicksort I'd guess it is
> O(N**2) or worse, worst case, as well.
timsort is actually a mergesort, not a quicksort.
You may like to read this:
http://svn.python.org/projects/python/trunk/Objects/listsort.txt
> Typical case of a sort is still O(N*log(N)) whether using key or cmp.
> People recommended against cmp not because of overall algorithmic time
> considerations, but because of the number of function calls. cmp
> function was called a minimum of N-1 times and typically around N*log2
> (N) times, whereas key was called exactly N times. Since the overhead
> of a Python function call was very large compared to the built-in cmp
> operation, it usually outweighed the algorithmic time considerations.
Yes, that sounds more like it. Thanks for the corrections.
--
Steven
More information about the Python-list
mailing list