array, list, performance...

[Aahz]

In article <mailman.1023369012.10674.python-list at python.org>,
Michael Chermside  <mcherm at destiny.com> wrote:
>
>    li.sort()      sort is O(len(li)*ln(len(li)))
>                   (I believe it uses quicksort, but if a python
>                    function has to be executed for the compare
>                    that may take some time.)

Nope.  I forget what Uncle Timmy used as his base, but while the
algorithm is O(NlogN) like quicksort, worst-case time is significantly
improved over quicksort's worst-case O(N^2), and the algorithm is
specifically designed to minimize compares precisely because even if a
Python function isn't listed for L.sort(), if L contains Python class
instances, it's quite likely to call instance methods.
-- 
Aahz (aahz at pythoncraft.com)           <*>         http://www.pythoncraft.com/

"I had lots of reasonable theories about children myself, until I
had some."  --Michael Rios