Jonathan Gardner <jgard...@jonathangardner.net> 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. -- http://mail.python.org/mailman/listinfo/python-list