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

[Dmitri Gribenko]

On Sun, Jan 10, 2016 at 3:11 PM, Davide Italiano <dccitaliano at gmail.com> wrote:
> Feedback very appreciated.
>
> Add stableSort() to the standard library.

Thank you for the proposal!  It is much appreciated!

> ####
> 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

We should also add an overload that takes a comparator closure.

> #####
> 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).

I have been thinking about this, and even though other languages it is
a separate function, since the fundamental operation of sort() and
stableSort() seems sufficiently similar to me, the defaulted parameter
seems like the right thing to do.  What other parameters could sort()
conceivably get in future?  Should the parameter be a boolean flag or
a resilient option set?  Foundation has NSSortOptions, which has just
"Stable" and "Concurrent".  The "concurrent" part, in my opinion,
needs to be handled somehow for all algorithms in a consistent manner,
rather than adding flags for each API separately.

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

Absolutely!

Dmitri

-- 
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr at gmail.com>*/