[swift-evolution] Add stableSort() to the standard library.

[Davide Italiano]

Feedback very appreciated.

Add stableSort() to the standard library.

####
Introduction
####
At the time of writing the Swift standard library provides two way two
different versions of sort.
The first one is sort(), which provides a regular unstable[1] sorting algorithm.
The second one, sortInPlace(), which also provides unstable sorting with the
additional guarantee that the algorithm will operate in-place, i.e., it will
use only a constant amount of extra space (independent from the input size).
The aim of this proposal is to implement a third variant, stableSort(), in order
to provide a stable version of sorting.

####
Motivation
####
Stable sorting is useful when sorting lists by multiple keys
(primary/secondary). A classical example is provided in [2].
Other programming languages, e.g. C++ or Go provide interfaces for stable
sorting in their standard libraries (respective std::stable_sort and Stable()).

#####
Proposed solution
#####
The API proposed just mirrors the one of regular sort().

@warn_unused_result func stableSort() -> [Self.Generator.Element]
Return an Array containing the sorted elements of source.

Discussion
The sorting algorithm is stable (does not change the relative order of elements
that compare equal).

Requires: The less-than operator (func <) defined in the Comparable conformance
is a strict weak ordering over the elements in self.

Constraints
Self.Generator.Element : Comparable

#####
Impact on existing code
#####
None.

####
Alternatives considered
####
An alternative would be that of augmenting sort() to get a Bool as argument
(stable: True). I'd rather like better to mirror what almost every
other programming
language does (providing a separate API).
It's an API breaking change (I think, but I'm not entirely sure).

####
Open questions
####
Should we also provide a stableSortInPlace() implementation?


Notes:

[1] A sorting algorithm is said to be "stable" if it maintains in the output
the relative order of entries with equal keys, and "unstable" otherwise.
[2] http://stackoverflow.com/questions/808617/what-is-the-benefit-for-a-sort-algorithm-to-be-stable/808658#808658

Thanks,

--
Davide