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

[Dmitri Gribenko]

On Mon, Jan 11, 2016 at 7:40 AM, Daniel Vollmer via swift-evolution
<swift-evolution at swift.org> wrote:
> Hello,
>
>> On 11 Jan 2016, at 04:39, Dmitri Gribenko via swift-evolution <swift-evolution at swift.org> wrote:
>
> [snip]
>
>> I have been thinking about this, and even though other languages it is
>> a separate function, since the fundamental operation of sort() and
>> stableSort() seems sufficiently similar to me, the defaulted parameter
>> seems like the right thing to do.  What other parameters could sort()
>> conceivably get in future?  Should the parameter be a boolean flag or
>> a resilient option set?
>
> Whether a sort should be stable or not doesn’t really strike me as a (variable) parameter (i.e. context of the sort() call determines whether a stable sort is needed).

Yes, I understand this.  However, consider other cases when you would
typically pass a constant at the call site --
Array.removeAll(keepCapacity:), for example.  The 'keepCapacity'
argument is typically a constant.  Do you feel like this API would be
better expressed as two methods?

> I would also assume that the algorithms implemented would be different for stable vs. unstable (unless of course unstable sort is implemented in terms of stable sort).

Also true, but even the unstable sort will check the array length and
use different implementations based on that.  So while a naive
implementation of `sort(stable:)` will only check the flag and switch
algorithms based on that, the implementation used in practice will be
more complex.

But, one thing that we need to ensure is that the generic specializer
and inliner are good enough to not produce extra code bloat for the
case when `sort(stable:)` is passed a constant.

Dmitri

-- 
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr at gmail.com>*/