key and cmp are equivalent for non-trivial cases (defined below), and for trivial cases the performance will be a trade-off between more function calls with cmp versus more memory use with key. Granted, for the smallish lists that the majority of Python sorts are done on, key is probably the better choice.
Non-trivial: Any time the user decides to (1) cache intermediary results for a cmp function or (2) define a __cmp__ function for the key return value. These arise when comparison of partial keys is often sufficient to establish order between two objects. -- http://mail.python.org/mailman/listinfo/python-list
