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

[Dave Abrahams]

on Sun Jan 10 2016, Davide Italiano via swift-evolution <swift-evolution-m3FHrko0VLzYtjvyW6yDsg-AT-public.gmane.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.

A few thoughts:

1. The C++ stable sort algorithm draws on just nearly every other
   algorithm in the entire standard library, many of which we don't
   currently have in Swift.  Doing something similar would expand the
   algorithms we support, which IMO would be a good thing.

2. I am very intrigued with Python's argument that, for a
   general-purpose audience, stable sorting should be the default.  It's
   certainly more widely-useful than unstable sorting.

3. There are several interesting and fast stable sorting algorithms out
   there, including Python's timsort; it would take some experimentation
   to discover which one(s) to use for Swift.

4. I'm not a fan of adding a parameter to sort to select stability,
   because of the added API complexity.  People who want a
   faster-but-unstable sort can call unstableSort, right?

-Dave