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

[Dave Abrahams]

on Thu Jan 21 2016, Charles Kissinger <crk-AT-akkyra.com> wrote:

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

That's true, but if that's the case we could (and should) select the
algorithm accordingly.  It's all statically-knowable, so shouldn't even
cost a branch in practice.

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

Maybe not.  If you look around, you'll find timsort has a handful of
competitors we also ought to examine.

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

True; that's what the current algorithm does.

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

A real question.  There's a lot of research to do, here.  If someone
wanted to take on this investigation and do a thorough job of it, I'm
sure it would have a big impact.

Cheers,
Dave