Should we take this opportunity to make the default sort a stable sort, instead of adding it as an afterthought?
If we take a "safety first" view of Swift algorithms, then a stable sort is strictly safer than a non-stable one, and should be a non-breaking change (because nobody should be depending on the specific idiosyncrasies of how equivalently-ordered data ends up actually ordered in the results of a non-stable sort).
As for a specific algorithm, there are people more knowledgeable in this space than I, but what about considering Timsort? (edit: beaten!)