
[Steven D'Aprano <steve@pearwood.info>]
... All I intended was to say that sort would "work" in the sense you state: it will give *some* permutation of the data, where (I think, correct me if I'm wrong) each element compares less than the following element.
Wait, no, that's not right either... each element doesn't compare less than the previous element?
There's really nothing useful that can be said without knowing precise implementation details, and essentially nothing at all that can be said about sorting-in-general, when a total order doesn't exist. Even for a 2-element list! If the result of Python's sort is [x, y] then I happen to know (because I know everything about its implementation) that one of two things is true: - The original list was also [x, y], and y < x was False. But we can't deduce anything about what x < y, x <= y, x == y, x != y. x > y, x >= y, y <= x, y > x, y >= x, y == x, or y != x would do. - The original list was [y, x], and x < y was True (but again we can't deduce anything about what any other comparisons involving x and y would do). For longer lists it can get much more complicated; comparing adjacent elements is just the first step in an algorithm with several stages, which dynamically adjust to patterns of comparison outcomes that are discovered as the algorithm goes along. If we don't know the precise implementation, there's really nothing crisp I can think of that necessarily follows from that the result is [x, y]. And I think this must be so for any "reasonably efficient" sorting algorithm. If there are N elements in the list, there are N*(N-1) _possible_ pairwise __lt__ invocations that could be made, but an efficient sort will never invoke more than O(N*log(N)) of them. The ratio of comparisons made to the number that _could_ be made tends to 0 as N increases - and in that sense the sort explores "almost none" of the possible comparison outcomes. For that reason, it would be much more expensive to check that a consistent total order exists than to do the sort. For the same reason, you can't deduce much from the result without knowing precisely which of the "nearly all of 'em" possible comparisons were skipped.