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