This comes up every few years, but that's about it.  Here's the iteration from 2 years ago:

https://mail.python.org/pipermail/python-ideas/2016-October/043039.html

Follow the thread.  It contains easy-to-use wrappers for both "do it in multiple simple passes" and "do it in one messy pass" approaches.  It's impossible for an implementation to guess in advance which will be faster - it depends on the data, which only the user can know about in advance.  There's nothing the implementation could do to improve O() behavior regardless.

If there were "real" demand for this, someone by now would have packaged those wrappers and made them available on PyPI.  Since that seems not to have happened, I agree with Raymond rejecting this idea for the core at this time.  There would be a higher-than-usual bar for that anyway, because the sorting code is already highly complex, and building in the wrappers would be a tedious, long-winded exercise in recoding in C what's _easily_ coded in Python already.