[Starter Proposal] Add Stable Sort to StdLib

[xwu (Xiaodi Wu)]

@allevato

Scalars are Equatable, and as @Ben_Cohen mentioned above, since Equatable implies substitutability, so I think the following approach would be a good compromise of performance and least-surprise:

A sort function constrained over Equatable elements (which in reality would mean Comparable because we’d want to use the element’s own < operator for comparison) could be specialized as an unstable sort.
A sort function that takes a custom comparator predicate would be stable.

I think this is muddying the waters. As explained in the documentation for Equatable, identity is not equivalence. Those are two distinct concepts. We should not use conformance to Equatable (i.e., a notion of equivalence) to be a proxy for judging whether instances of that type have a notion of identity.

As far as I'm aware, Swift always provides the most correct implementation as the default or currency option. Those who wish to opt into more performance can explicitly invoke alternatives (e.g., unsafeAdding vs. +).