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 _______________________________________________ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/Q5RFMMCWHVEX2EIN4LIYPX5YXXDAI5PG/ Code of Conduct: http://python.org/psf/codeofconduct/
