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

[ankit goel]

Hey,

A single sort function with an enum parameter that let's you choose among
sort(), sortInPlace() and stableSort() would be nice.

enum SortOptions {
  case none
  case InPlace
  case Stable
}

func sort(items, type: SortOptions = .none)

// call to sort function
sort([1,2,3,4], type: .Stable)

This way a single sort function handles all three cases and enums provide
autocompletion while calling the function.


On Fri, Jan 22, 2016 at 3:22 AM, Dave Abrahams via swift-evolution <
swift-evolution at swift.org> wrote:

>
> 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
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160122/6d9c32b9/attachment.html>