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

[Kenny Leung]

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


> 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