[David Mertz <david.me...@gmail.com>] > Thanks Tim for clarifying. Is it even the case that sorts are STABLE in > the face of non-total orderings under __lt__? A couple quick examples > don't refute that, but what I tried was not very thorough, nor did I > think much about TimSort itself.
I'm not clear on what "stable" could mean in the absence of a total ordering. Not only does sort not assume __lt__ is a total ordering, it doesn't assume it's transitive, or even deterministic. We really can't assume anything about potentially user-defined functions. What sort does guarantee is that the result list is some permutation of the input list, regardless of how insanely __lt__ may behave. If __lt__ sanely defines a deterministic total order, then "stable" and "sorted" are guaranteed too, with their obvious meanings. _______________________________________________ Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/
