We should consider biting the bullet and revising the default NaN sort order.  It has been a perpetual irritant.

1) Have NaNs always compare to less than any other float value.
2) When comparing two distinct NaNs, use the NaN payload
   and fall back to object id if necessary.
3) When comparing two identical NaNs, always return False.

That preserves the IEEE-754 guarantee that NaNs never compare equal to one another -- which is one of the few properties that people rely on.

IEEE-754 doesn't concern itself at all with the notion of object identity, so giving two NaNs a deterministic but unequal ordering isn't at odds with the standard.

IMHO, making min(), max(), and sorted() both deterministic and commutative is a big enough win to warrant foregoing one of the less important properties of NaN.  User care about determinism and commutativity more than they care that float('NaN') > 10 and float('NaN') < 10 both return False.

“Logic clearly dictates that the needs of the many outweigh the needs of the few.” -- Spock, The Wrath of Khan ;-)

Python is practical language, so we should consider making a choice based on pragmatism rather than strict standard compliance.  Bug reports like this are the tip of the iceberg.  Given the prevalence of NaNs being used as a placeholder for missing data, it is likely that people struggle with this every day.

The original design of NaNs was to let invalid intermediate results flow through a calculation and not require error testing at every step.  But in practice, NaNs are not commonly used this way.  Mainly, they are used as the float equivalent of None in an array of floats.  We should support this reality.  IMO it is a small disaster that NaNs completely wreck sorting and do so silently.  From user POV, an arcane property of NaNs is an inadequate justification for the misbehavior.