[Python-Dev] PEP 393 Summer of Code Project

[Terry Reedy]

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.

-- 
Terry Jan Reedy