<div dir="ltr">Hey,<div><br></div><div>A single sort function with an enum parameter that let's you choose among sort(), sortInPlace() and stableSort() would be nice.</div><div><br></div><div>enum SortOptions {</div><div> case none</div><div> case InPlace</div><div> case Stable</div><div>}</div><div><br></div><div>func sort(items, type: SortOptions = .none)</div><div><br></div><div>// call to sort function</div><div>sort([1,2,3,4], type: .Stable)</div><div><br></div><div>This way a single sort function handles all three cases and enums provide autocompletion while calling the function.</div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Jan 22, 2016 at 3:22 AM, Dave Abrahams via swift-evolution <span dir="ltr"><<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="HOEnZb"><div class="h5"><br>
on Thu Jan 21 2016, Charles Kissinger <crk-AT-akkyra.com> wrote:<br>
<br>
>> On Jan 20, 2016, at 9:58 AM, Dave Abrahams via swift-evolution <<a href="mailto:swift-evolution@swift.org">swift-evolution@swift.org</a>> wrote:<br>
>><br>
>><br>
>> on Sun Jan 10 2016, Davide Italiano via swift-evolution<br>
>> <<a href="http://swift-evolution-m3FHrko0VLzYtjvyW6yDsg-AT-public.gmane.org" rel="noreferrer" target="_blank">swift-evolution-m3FHrko0VLzYtjvyW6yDsg-AT-public.gmane.org</a>> wrote:<br>
><br>
>><br>
>>> Feedback very appreciated.<br>
>>><br>
>>> Add stableSort() to the standard library.<br>
>>><br>
>>> ####<br>
>>> Introduction<br>
>>> ####<br>
>>> At the time of writing the Swift standard library provides two way two<br>
>>> different versions of sort.<br>
>>> The first one is sort(), which provides a regular unstable[1] sorting algorithm.<br>
>>> The second one, sortInPlace(), which also provides unstable sorting with the<br>
>>> additional guarantee that the algorithm will operate in-place, i.e., it will<br>
>>> use only a constant amount of extra space (independent from the input size).<br>
>>> The aim of this proposal is to implement a third variant, stableSort(), in order<br>
>>> to provide a stable version of sorting.<br>
>><br>
>> A few thoughts:<br>
>><br>
>> 1. The C++ stable sort algorithm draws on just nearly every other<br>
>> algorithm in the entire standard library, many of which we don't<br>
>> currently have in Swift. Doing something similar would expand the<br>
>> algorithms we support, which IMO would be a good thing.<br>
>><br>
>> 2. I am very intrigued with Python's argument that, for a<br>
>> general-purpose audience, stable sorting should be the default. It's<br>
>> certainly more widely-useful than unstable sorting.<br>
><br>
> Stable sorting as the default would follow the Principle of Least<br>
> Astonishment, I think (especially for programmers coming from Python<br>
> and Java, where stable is the default). And the more widely useful<br>
> algorithm, even if it is at the expense of performance, seems like the<br>
> right choice for a standard library.<br>
><br>
>><br>
>> 3. There are several interesting and fast stable sorting algorithms out<br>
>> there, including Python's timsort; it would take some experimentation<br>
>> to discover which one(s) to use for Swift.<br>
><br>
> I suppose one complication for Swift is that any particular algorithm<br>
> might perform well with reference types but less so with value types<br>
> if they happen to be large and the algorithm does a relatively large<br>
> amount of copying.<br>
<br>
</div></div>That's true, but if that's the case we could (and should) select the<br>
algorithm accordingly. It's all statically-knowable, so shouldn't even<br>
cost a branch in practice.<br>
<span class=""><br>
>> 4. I'm not a fan of adding a parameter to sort to select stability,<br>
>> because of the added API complexity. People who want a<br>
>> faster-but-unstable sort can call unstableSort, right?<br>
><br>
> I wonder if anyone actually would be clamoring for an unstable sort<br>
> option, per se, given how well timsort seems to perform.<br>
<br>
</span>Maybe not. If you look around, you'll find timsort has a handful of<br>
competitors we also ought to examine.<br>
<span class=""><br>
> An algorithm, stable or unstable, with lower memory requirements or<br>
> different edge case behavior might be the most useful alternative. For<br>
> instance, an algorithm that sorts in-place without any significant<br>
> memory overhead (“in-place" not in the mutating sense, but in not<br>
> requiring temporary storage during the sort) could be handy when<br>
> dealing with large sequences on more memory-constrained<br>
> devices.<br>
<br>
</span>True; that's what the current algorithm does.<br>
<span class=""><br>
> Still, I wonder if it will really be a pain point for anyone<br>
> if the only option is a state-of-the-art stable sort.<br>
<br>
</span>A real question. There's a lot of research to do, here. If someone<br>
wanted to take on this investigation and do a thorough job of it, I'm<br>
sure it would have a big impact.<br>
<br>
Cheers,<br>
<div class="HOEnZb"><div class="h5">Dave<br>
_______________________________________________<br>
swift-evolution mailing list<br>
<a href="mailto:swift-evolution@swift.org">swift-evolution@swift.org</a><br>
<a href="https://lists.swift.org/mailman/listinfo/swift-evolution" rel="noreferrer" target="_blank">https://lists.swift.org/mailman/listinfo/swift-evolution</a><br>
</div></div></blockquote></div><br></div>