[Tim]
.... 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.
[Steven]
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 code doesn't even assume that x == x holds - or that x < y will return the same value if called a second time. When user-supplied operators are called, nothing can be assumed. This isn't empty ;-) There's a long history of segfaults due to assuming _any_ kind of sanity in user-supplied code.
- 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?
I'm not sure what this is about. In both cases above, I'm referring to elements by their names in the second (output) list, but they're treated exactly the same way in the original list. If the list is named, say, "values", the only comparison done is values[1] < values[0] If that's True, the values are swapped; if False, they're left alone.
My understanding was that the direction of comparisons was controlled by the reverse parameter.
If reverse=True is passed, values[1] < values[0] is _still_ the only comparison done (although, as about to be explained, the elements are swapped _before_ the sort sees them). `reverse` has no effect whatsoever on any internal step of the algorithm. Instead it's a pre/post-processing gimmick: values.sort(reverse=True) acts like, and is actually _implemented_ as: values.reverse() values.sort() values.reverse() This is subtle, and the docs could be clearer about what it means by "as if each comparison were reversed", I didn't write that (I didn't implement "reverse=" either). but appreciate that what it's trying to say is subtle. It's NOT the same as: values.sort() values.reverse() and in my experience barely anyone knows why. It's to make list.sort() stable even if reverse=True is passed: equal items remain in the their original order regardless of the value of the reverse flag. The second shorter spelling would violate stability, but the first longer spelling preserves it (the order of equal items is first reversed, then the stable regular sort preserves that reversed order, and then the final reverse restores the original order of equal items).
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?
Still not clear what the question is, but hope the above answered it. In particular, the reverse flag is mostly a red herring.
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?
I really don't know! It sounds plausible ;-) , for the current sort implementation, which is a mix of strategies mostly based on binary search and merging. Offhand I couldn't think of a counterexample - but their was no _intent_ to make that so. It's not true of sorts in general. For an easy example, here's a simple stable(!) quicksort, based on 3-way partitioning (extremely effective in the presence of many equal elements): def quick3(xs): from random import choice if len(xs) <= 1: return xs lt = [] eq = [] gt = [] pivot = choice(xs) for x in xs: if x is pivot or x == pivot: # "is" to guard against insane __eq__ eq.append(x) elif x < pivot: lt.append(x) else: gt.append(x) return quick3(lt) + eq + quick3(gt) Pass it the list [1, 2a. 2b. 2c. 3] where the three instances of "2" are tagged with letters so we can visually distinguish them. If the pivot is 2b, then the only comparisons ever done involve 2b, the output list is the same, but 1 is never compared with 2a nor is 2c ever compared with 3.