On Mon, Mar 09, 2020 at 04:50:49PM -0500, Tim Peters wrote:

[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,

Understood, I'm not discussing sorting in general, I'm discussing Timsort specifically :-)

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.

That's my reasoning, based on your earlier example with the list of three sets.

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.

This doesn't surprise me, because comparison methods are independent of each other and the law of trichotomy doesn't necessarily hold.

- 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).

Now *that* surprises me! Should I understand from this that the direction of comparisons (whether timsort compares `x < y` or `y < x`) could be chosen arbitrarily? My understanding was that the direction of comparisons was controlled by the reverse parameter. So if we're referring only to the default reverse=False, the comparisons must go in one direction rather than the other. Is that wrong?

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.

Ack. But my expectation is that by the time all the complicated stuff was done, we might not know all the gory details of what elements got compared, and we don't know anything about any "global" order over the entire set, but we do know the "local" order: if x ends up next to y, then *at some point* in the sorting x must have been compared to y and so we know that y doesn't compare less than x. Is this not accurate? Thanks for the fascinating glimpse into timsort. -- Steven