I dunno, the whole reason we’re having this discussion is because of a fear that people have taken a dependency on a stable sorting algorithm without even noticing that stability is a property to be analyzed. If this is something so important and so subtle, then it seems worth mentioning it in any future API names.
+1 stable sounds great for the default name.
I sort of think that the naming discussion is a whole other issue that could be added to the algorithms package.
I'm in favor of officially making sort stable. It's one less trap people can fall into that makes the language nicer to use.
I see "unstable" sort a bit like "unsafe" pointers: good to have, possibly better for performance, but also easier to misuse. It shouldn't be the default sort.
9 Likes
This is also great for progressive disclosure. Beginners to programming intuitively think of sorting as stable, or at least I did, which is what sort should reflect. On the other hand, someone coming to Swift from a (low-level) programming background, should know to look at documentation. If Swift were used mostly for low-level algorithms, I think stableSort and unstableSort with a deprecated sort would be fine, but that’s not the case and these methods would instead add extra info that would just be noise to some users.
4 Likes
I also think so. When someone needs a custom sorting algorithm the tradeoff is often between memory consumption and computational burden.
In my own practice it is really so. When they sorted things like products, contacts, cities etc. by name, they were very surprised when the result is sometimes different and elements with the same name sometimes swaped.
2 Likes
I am fully on board for guaranteeing that sorting is stable. It's been stable since before Swift 5 anyway, and most people who'd be interested in a different sort probably have specific requirements on what kind of sort they need beyond just stable or unstable.
1 Like
+1 let’s lock it in.
The niche of a potentially more performant sort that happens to be unstable sounds like something that depends more on the individual case at hand. As such, I believe that niche would be better served by a library of different sorting algorithms that users can depend upon for their specific use case.
I agree with the idea that a stable sort extends on the idea of Swift being “safe” by default. I’m not yet convinced we need to add an “unsafe” variant to the stdlib (regardless of how we spell it) but, if we do, that should be a separate thread / pitch.
3 Likes
+1 to this documentation change. It’s well-known across the entire Internet and Swift community that Swift’s sort behaves stably, so making this documentation change seems like a reasonable codification of the collective mind of the Internet.
It’s also a good way to move on from a high-profile distraction in the standard library.
The separate question on whether the method needs to be named more appropriately (or broken into multiple methods) can be answered by looking at the expectation of the developer when they hear the word “sort”. Is there any reasonable expectation by the beginner (or even the expert in an average use case) for there to be an unstable behavior? I think the answer is “no” in most cases, so the existing method can keep its current name. When I learned to code in college some years back, I never expected a sorting algorithm to be unstable - it usually “just worked”. Now, as I’m more experienced, I look at this as possibly being on the verge of a meme. Of course it’s stable - there’s only one sort variant, so would the only one ever be unstable? Probably not.
Is there legitimate desire for an unstable sorting method, just for the sake of instability? Probably not, unless you’re looking to make another meme out of the standard library sorting.
Sort stability is a fringe/obscure detail (IMO) that I’m sure most students and beginner developers don’t really care or think about. Is it important for experts? Yes - and it’s also distracting, so let’s make the documentation change and move on!
6 Likes
Allow me to add some hard-won perspective from another library; the MATLAB language went through the same growing pains in the late 2000's - we never documented the builtin sort function as stable, but it happened to be stable.
When approached with an alternate, non-stable implementation that sped up sorting by orders of magnitude, the library Steering Committee (of which I was a member) approved, wholeheartedly. After all, the sort performance was a huge source of client complaints, and it was never guaranteed to be stable!
As several people have pointed out in this thread, the concept of an "unstable" sort doesn't even occur to many developers. When this change shipped, you could hear the uproar from across the ocean!
I wish that we had initially documented the function as non-stable, but I don't know that would have helped. Once the stability cat is out of the bag, you will hear about any regressions, hard.
For that reason, I (sadly) recommend documenting that sort implementations are expected to be stable, and add a different, undocumented, non-stable sort function. I'm agnostic re. the spelling.
20 Likes
I have to ask, what algorithm did your move from and to?
Sorry, but that was about 15 years ago - I have no idea!
Thanks for the feedback, everyone! I've updated the proposal and opened a PR here: Add 'Document Sorting as Stable' proposal by natecook1000 · Pull Request #1770 · apple/swift-evolution · GitHub
5 Likes