I think it’d probably be fine if the stable sort was even the default, and you had to opt into the higher performance version.
I agree. My preferred solution would be to convert the existing sort to be stable would be the best move, and to introduce sortUnstably (not great naming I know but I’d really prefer it start with the word “sort”). This would be in keeping with the choice most other languages have made.
Adding sortUnstably and adding a stability guarantee to the existing definition would need an evolution proposal, but re-implementing the existing sort to be stable instead of unstable wouldn't, necessarily, since it's just an implementation detail, so long as we can keep to the current complexity guarantee. There's good reason to believe this re-implementation could be a performance improvement in some cases even when switching to a stable sort. I've opened a thread over on the std lib dev forum to discuss the implementation.