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