python 3's adoption

Paul Rubin at nospam.invalid
Thu Jan 28 01:30:40 CET 2010

Jonathan Gardner <jgardner at> writes:
> 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.

It's O(n log n) for both key and cmp.  key is usually more convenient
and usually gives a constant-factor speedup (DSU pattern), but it uses
more memory and there are some types of orderings that it can't handle
without a bunch of contortion.

More information about the Python-list mailing list