[Python-Dev] PEP 393 Summer of Code Project

["Martin v. Löwis"]

Am 27.08.2011 09:40, schrieb Steven D'Aprano:
> Terry Reedy wrote:
>> On 8/26/2011 8:23 PM, Antoine Pitrou wrote:
>>
>>>> I would only agree as long as it wasn't too much worse
>>>> than O(1). O(log n) might be all right, but O(n) would be
>>>> unacceptable, I think.
>>>
>>> It also depends a lot on *actual* measured performance
>>
>> Amen. Some regard O(n*n) sorts to be, by definition, 'worse' than
>> O(n*logn). I even read that in an otherwise good book by a university
>> professor. Fortunately for Python users, Tim Peters ignored that
>> 'wisdom', coded the best O(n*n) sort he could, and then *measured* to
>> find out what was better for what types and lengths of arrays. So not
>> we have a list.sort that sometimes beats the pure O(nlog) quicksort of
>> C libraries.
> 
> A nice story, but Quicksort's worst case is O(n*n) too.

In addition, timsort is O(n log n), which also makes it a real good
O(n*n) sort :-)

Regards,
Martin