[David Mertz
OK, let me be more precise. Obviously if the implementation in a class is:
class Foo: def __lt__(self, other): return random.random() < 0.5
Then we aren't going to rely on much.
* If comparison of any two items in a list (under __lt__) is deterministic, is the resulting sort order deterministic? (Pretty sure this is a yes)
Yes, but not defined unless __lt__ also defines a total ordering.
* If the pairwise comparisons are deterministic, is sorting idempotent?
Not necessarily. For example, the 2-element list here swaps its elements every time `.sort()` is invoked, because the second element always claims it's "less than" the first element, regardless of which order they're in: class RelentlesslyTiny: def __init__(self, name): self.name = name def __repr__(self): return self.name def __lt__(self, other): return self is not other a = RelentlesslyTiny("A") b = RelentlesslyTiny("B") xs = [a, b] print(xs) xs.sort() print("after sorting once", xs) xs.sort() print("after sorting twice", xs) [A, B] after sorting once [B, A] after sorting twice [A, B]
This statement is certainly false:
* If two items are equal, and pairwise inequality is deterministic, exchanging the items does not affect the sorting of other items in the list.
What I said at the start ;-) The only thing .sort() always guarantees regardless of how goofy __lt__ may be is that the result list will be some permutation of the input list. This is so even if __lt__ raises an uncaught exception, killing the sort mid-stream.