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

[Charles Kissinger]

> On Jan 20, 2016, at 9:58 AM, Dave Abrahams via swift-evolution <swift-evolution at swift.org> wrote:
> 
> 
> 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.

Stable sorting as the default would follow the Principle of Least Astonishment, I think (especially for programmers coming from Python and Java, where stable is the default). And the more widely useful algorithm, even if it is at the expense of performance, seems like the right choice for a standard library.

> 
> 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.

I suppose one complication for Swift is that any particular algorithm might perform well with reference types but less so with value types if they happen to be large and the algorithm does a relatively large amount of copying.

> 
> 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?

I wonder if anyone actually would be clamoring for an unstable sort option, per se, given how well timsort seems to perform. 

An algorithm, stable or unstable, with lower memory requirements or different edge case behavior might be the most useful alternative. For instance, an algorithm that sorts in-place without any significant memory overhead (“in-place" not in the mutating sense, but in not requiring temporary storage during the sort) could be handy when dealing with large sequences on more memory-constrained devices. Still, I wonder if it will really be a pain point for anyone if the only option is a state-of-the-art stable sort.

—CK

> -Dave
> 
> 
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution