On 3/9/20 7:45 AM, Steven D'Aprano wrote:
On Mon, Mar 09, 2020 at 06:39:10AM -0400, Richard Damon wrote:
On 3/9/20 12:41 AM, Steven D'Aprano wrote:
Wait, no, that's not right either... each element doesn't compare less than the previous element?
If the elements of the list don't form a total order, then sort makes NO promises about the data returned, other than it is the input data in some order. I think we can tell more than that from the guarantee that sort only calls `<` and not any other comparison.
If the output of sort is [a, b, c, d] then I think that we know that:
b < a returns False c < b returns False d < c returns False
but not necessarily anything else.
I'm making this judgement based on Tim's earlier post, where he describes the comparisons used in sorting a list of sets, not from reading the source code or experimentation. There may be more, or less, that we can be sure about.
For example, I'm confident that sort has to do at least one comparison on each element (there are no elements that never get looked at; every element gets inspected at least once).
I'm also confident (absolutely sure actually) that it *doesn't* compare every *pair* of elements. But it might compare every pair of *consecutive* elements.
Of course this isn't a language guarantee, it will depend on the implementation. Bubblesort will probably behave very differently from Heapsort. But we know the implementation used in CPython, and that's what I'm discussing.
But you can create a type that behaves sufficiently bad that it can't do that. Say we have the opposite of a NaN, lets call it an AnA (its any number), that return true for all comparisons, since there is some number that makes the comparison true. Such a type first makes your guarantee impossible, and will totally mess up any algorithm that is based on transitivity (if a < b and b < c then a < c, since if b is an AnA that won't necessarily hold). NaNs perhaps cause a smaller problem because people tend to not use the form of transitivity that comes from a total order in the negative, i.e. if a is not less than b, and b is not less than c, then a is not less than c. -- Richard Damon