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

[Charles Kissinger]

> On Jan 11, 2016, at 9:51 AM, Kenny Leung via swift-evolution <swift-evolution at swift.org> wrote:
> 
> I can’t imagine a case where one wouldn’t want this, so why not just replace the existing sort with the stable sort?
> 
> -Kenny
> 

It’s primarily a performance issue, I think. The best unstable sort algorithms are faster and/or use less memory, as I understand it. Are they enough faster to make a difference to most people? I don’t know.

-CK

> 
>> On Jan 10, 2016, at 3:11 PM, Davide Italiano via swift-evolution <swift-evolution at swift.org> wrote:
>> 
>> 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
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution at swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
> 
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution