[Python-ideas] NAN handling in the statistics module

Tim Peters tim.peters at gmail.com
Sun Jan 6 23:09:03 EST 2019

[David Mertz <david.mertz at 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.

More information about the Python-ideas mailing list