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/

Reply via email to