array, list, performance...

Aahz aahz at
Thu Jun 6 16:36:56 CEST 2002

In article <mailman.1023369012.10674.python-list at>,
Michael Chermside  <mcherm at> 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           <*>

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

More information about the Python-list mailing list