Am I the only one that thinks this is a stupid decision? This will silently break code that starts to rely on this behaviour that gets executed on Python3.5 and lower. I would consider changing how a builtin works to be a major breaking change. It would have been fine if this was a change between 2 and 3 but on a minor version? Thats insane.
I'm not clear on how this break existing code. Code that assumed it was arbitrary, would expect to handle any arbitrary order, including a happens-to-be sorted order. Code that assumed it was random, like actually inserted by random(), was already broken, because that simply isn't the case. Code that assumed the order would stay constant was relying on implementation-specific behavior, and could potentially break on…
I think TimSort is extremely efficient for presorted lists, so even that isn't a major impediment.