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
_______________________________________________
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/LVD7APIUTWN3LN5HA5EOKXRWEVE7WKJF/
Code of Conduct: http://python.org/psf/codeofconduct/
