[swift-evolution] Add stableSort() to the standard library.
Dave Abrahams
dabrahams at apple.com
Wed Jan 20 15:13:34 CST 2016
on Wed Jan 20 2016, Tyler Cloutier <cloutiertyler-AT-aol.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
>
>> <http://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?
>
> I think the potential here is that people might not even be aware
> there is such an option. unstableSort() not terribly autocomplete
> friendly which I think adds to complexity.
sortFasterButUnstably, then ;-)
> It seems like a parameter
> would be in line with API’s like print(_:separator:terminator:), even
> though the print arguments are not constants. I think the print API is
> very intuitive, but perhaps I’m misunderstanding what you mean by
> complexity?
No, I think you understand me.
-Dave
More information about the swift-evolution
mailing list