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

[Davide Italiano]

On Sun, Jan 10, 2016 at 7:39 PM, Dmitri Gribenko <gribozavr at gmail.com> wrote:
> 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.
>

I think you convinced me that passing a parameter to sort() is the
right way to go. About NSortOptions -- I'm not completely sure
(still).
I think it largely depends on the number of options we want to
provide, and I see pro/cons in both the approaches.

* If we change sort to take a Bool as argument, and then suddenly
realize we need another option (as you noted, Concurrent), then we
need to break the API again and make that more verbose. If the number
of options grows under a certain number the verboseness of the API
might start becoming a problem (although I don't think this is the
case for sort()).

* If we change sort to take NSOptions -- and then the number of
options to pass doesn't grow (in the worst, somewhat terrible case, we
don't introduce any other options other than `stable`), then we lose
in usability. It's sort of goofy providing an API with Options which
take a single option.

So, my preference is for passing a Bool to sort(), and *eventually*
re-evaluate if needed. I think my guiding principle is trying to not
violate the YAGNI/KISS principles. But I'm open to comments if
somebody disagrees =)

Thanks!

--
Davide