<div dir="ltr"><div>OK, let me be more precise.  Obviously if the implementation in a class is:</div><div><br></div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><div><font face="monospace, monospace">class Foo:</font></div><div><font face="monospace, monospace">    def __lt__(self, other):</font></div><div><font face="monospace, monospace">        return random.random() < 0.5</font></div></blockquote><div><font face="monospace, monospace"><br></font></div><div>Then we aren't going to rely on much.  </div><div><br></div><div>* If comparison of any two items in a list (under __lt__) is deterministic, is the resulting sort order deterministic? (Pretty sure this is a yes)</div><div>* If the pairwise comparisons are deterministic, is sorting idempotent?</div><div><br></div><div>This statement is certainly false:</div><div><br></div><div>* If two items are equal, and pairwise inequality is deterministic, exchanging the items does not affect the sorting of other items in the list.</div><br><div class="gmail_quote"><div dir="ltr">On Sun, Jan 6, 2019 at 11:09 PM Tim Peters <<a href="mailto:tim.peters@gmail.com">tim.peters@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">[David Mertz <<a href="mailto:david.mertz@gmail.com" target="_blank">david.mertz@gmail.com</a>>]<br>
> Thanks Tim for clarifying.  Is it even the case that sorts are STABLE in<br>
> the face of non-total orderings under __lt__?  A couple quick examples<br>
> don't refute that, but what I tried was not very thorough, nor did I<br>
> think much about TimSort itself.<br>
<br>
I'm not clear on what "stable" could mean in the absence of a total<br>
ordering.  Not only does sort not assume __lt__ is a total ordering,<br>
it doesn't assume it's transitive, or even deterministic.  We really<br>
can't assume anything about potentially user-defined functions.<br>
<br>
What sort does guarantee is that the result list is some permutation<br>
of the input list, regardless of how insanely __lt__ may behave.  If<br>
__lt__ sanely defines a deterministic total order, then "stable" and<br>
"sorted" are guaranteed too, with their obvious meanings.<br>
</blockquote></div><br clear="all"><div><br></div>-- <br><div dir="ltr" class="gmail_signature">Keeping medicines from the bloodstreams of the sick; food <br>from the bellies of the hungry; books from the hands of the <br>uneducated; technology from the underdeveloped; and putting <br>advocates of freedom in prisons.  Intellectual property is<br>to the 21st century what the slave trade was to the 16th.<br></div></div>