> We should consider biting the bullet and revising the default NaN sort order.

If we went that route, I think we wouldn't need to consider payload or identity. We could just do:

        NaN < NaN      ->  False
        NaN < non-NaN  ->  True
    non-NaN < NaN      ->  False
    non-NaN < non-NaN  ->  usual numeric comparison

That then satisfies the axioms for a total ordering, albeit that the implied equality isn't Python's == (and it can't be, if we're going to keep the property that NaN != NaN): all NaNs compare equal for the equality determined by the above order, and the stability of the sort means that those NaNs will retain their order relative to each other in the sorted output.

Making `NaN < non-NaN` return `True` (which happens under both the proposal above and Raymond's more elaborate proposal) _would_ be a break with IEEE 754, though.

There's also a somewhat arbitrary choice to be made here: do we consider NaNs to be negative or positive? That is, do we want NaNs to sort to the beginning of the list, or the end?