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

[Davide Italiano]

On Sun, Jan 10, 2016 at 10: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.
>
>> ####
>> 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>*/

So, thank you all for the feedback.
I'll refine this proposal further, but I have a question.
Should we continue here (and I should paste a new version of the
proposal) -- or should I submit a new pull request to
apple/swift-evolution on github so that interested parties can comment
there?

Thanks,

--
Davide