SE-0372: Document Sorting as Stable

Hello Swift community,

The review of SE-0372: "Document Sorting as Stable" begins now and runs through September 20, 2022.

Reviews are an important part of the Swift evolution process. All review feedback should be either on this forum thread or, if you would like to keep your feedback private, directly to the review manager. When emailing the review manager directly, please keep the proposal link at the top of the message.

What goes into a review?

The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift. When writing your review, here are some questions you might want to answer in your review:

  • What is your evaluation of the proposal?
  • Is the problem being addressed significant enough to warrant a change to Swift?
  • Does this proposal fit well with the feel and direction of Swift?
  • If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?
  • How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

More information about the Swift evolution process is available at

https://github.com/apple/swift-evolution/blob/main/process.md

Thank you,

—Tony Allevato
Review Manager

37 Likes

Please, yes. Definitely for, it's a natural progression to the API that has been stable, and I'd very much like to have that guarantee included.

3 Likes

Absolutely +1.

2 Likes

An emphatic +1!

This has long been one of my biggest gripes with the standard library. It will be great to see it fixed.

3 Likes

A SE proposal to remove exactly one word from a comment has got be establishing a record of some kind! :) +1 from me!

5 Likes

This is a no-brainer.

We should write some expanded documentation that shows what a "stable" sort means, practically (including negative examples), but that can be a follow-on task separate from this proposal.

7 Likes

+1

Are we sure that stable-sorting is actually what people really need?

In my experience, people want stable-sorting because they want to compose multiple sort criteria together. We don't have a great API for this, so they cobble it together with something like:

let sortedContacts = contacts
    .sorted(by: \.lastName) // 2. Break ties by last name
    .sorted(by: \.firstName) // 1. Sort by first names

(which obviously only works if sorting is stable, in order for the relative order of the last names to persist after sorting by first names)

In fact, my most popular post on StackOverflow is about exactly this. @hamishknight 's answer to the same question is even more up-voted, with a whopping 173 upvotes.

I think it might first be more useful to explore some kind of compositional sort descriptor API, similar to how Foundation uses NSArray<NSSortDescriptor>.

If a need for stable sorting remains after that, then we can tackle it.

Luckily, there’s no tackling needed. Swift already has a stable sort, it’s just not documented as such.

By "it" I was referring to the question about whether we should document it as such, and if so, what should be its name.

I think the more important first step is to solve (what I think to be) is the main thing making people reach for a stable sort where they otherwise might not have needed it.

Stable sorting is desirable with or without such a feature. There is already some ordering on elements to be sorted, and preserving that order is almost never harmful, and often beneficial.

If someone is implementing a UI that allows sorting on columns, the expectation is that a "sort" operation will be stable, so that they can simply sort twice, rather than having to construct a chained sort query somehow.

Developing a compositional sort API is well worth considering, but does not take anything away from the value of documenting the existing sort as stable.

10 Likes

I'm not sure that's a relevant question? The sort is de-facto stable, as-is. Documenting it in accordance to the actual implementation is so basic, imho, I'm surprised it needed an evolution proposal to begin with.

If we ever need some future theoretical unstable sort, it would be an additive change. It could either be a new unstableSorted(by:) or a new overload spelled like stored(by:stable:), sorted(by:options:), or whatever.

That said, I think we could improve the ergonomics of our sorting APIs, and agree that a composable sorting criteria would be useful. I'm using a home grown SortDescriptor type in my projects, which has static constructors for the common cases, and sorted(by:) overloads for both single and variadic sort descriptors. But I guess that's for a future evolution proposal.

1 Like

I absolutely agree that we should explore adding sort descriptors to the standard library! In addition to allowing you to compose multiple search criteria, as highlighted in your Stack Overflow answer, sort descriptors also streamline and eliminate errors in sorting based on a single property. We've had a variety of pitches over the years for this feature, and I look forward to working together to bring something compelling to the Swift Evolution community.

That said, sort stability is an important question that can be considered separately at the current time, without waiting for more exploration. In addition to the reasons described in the proposal (it would be disruptive to change even un-guaranteed behavior at this point, and brings benefits to those who would like to rely on sort stability), a stability guarantee is important to have for future work.

Simulating a composed sort is demonstration of stability, but the semantic guarantee is really about preserving a collection's preexisting structure. In your example of sorting by last name and then first name, whether by multiple searches, a carefully written predicate, or by some future sort descriptor, stability preserves the existing ordering of other fields in the data. That is, if the contacts array is already sorted by creation date, a stable sort preserves that order for contacts with exact matches across both names.

Thanks for your feedback!

The various pitches that I could find, sorted from oldest to newest
3 Likes

Given that the standard sort function is an arbitrary choice of algorithm that might or might not change and might or might not be stable with each release, under what circumstances would relying on that be preferable to having an arbitrary choice of algorithm that is always stable?

Surely if stability not acceptable or desireable in a particular situation, whether for greater speed or perhaps some unusual reliance on an instability occurring, then you are going to have to be explicit in your choice and implementation of a custom algorithm no matter what guarantees the standard library provides.

In other words, under what circumstances would it be acceptable to use the built-in sort only if it is not guaranteed stable? Is guaranteed stability not all ups and no downs? What am I missing?

2 Likes

+1. From previous discussions (particularly Is sort() stable in Swift 5? - #11 by Ben_Cohen) the stability of the sort is de facto guaranteed already since changing the sort stability would essentially mean that sort behaves differently depending on target platform and that’s just not something that’s going to happen. This change clarifies that expectation without introducing any limitation with regards to future implementations of sorting algorithms with different attributes potentially requiring removing stability guarantees (since those can be provided as specific implementations with different APIs). I don't see any downside to this at all.

Hi folks,

The language workgroup has accepted this proposal. Thank you to all who participated!

9 Likes