Add stable sort algorithm

The standard library should provide a stable sorting algorithm, next to the
regular, unstable, sort() and sortInPlace().

This needs a proposal to swift-evolution (the design should be trivial, new
methods should mirror existing sorting APIs), and implementation. The
standard library already contains an internal implementation of insertion
sort, so implementing this should amount to providing public entry points
and writing tests.

via: SR-306

I am in favor of this.
https://bugs.swift.org/browse/SR-306

A solution is to drop to Objective-C,

There are well known stable sort algorithms that can maintain or improve performance, so we may not even need alternate version. @nnnnnnnn had a PR years ago that accomplished this but it was ultimately rejected for non-technical reason.

smfh they didn’t even get the meme right

you can stable sort anything by enumerating it and sorting lexicographically.

Not to be that guy, but given that there’s an open bug (and the fairly obvious nature of the feature), I see little reason to resurrect this thread without movement towards an implementation, which is what’s holding it back.

On a meta level, it seems that with easier searching there’s a spate of new messages posted to ancient threads that say little more than, “I want this.” Like “bump” messages in other forums, I’m not sure it’s moving the conversation forward in any material way.

2 Likes

i think this is a very positive thing, with the mailing list format it was easy for good ideas and widely desired feature requests to get “lost in the mail” and forgotten about whether from bad timing or just because the right person didn’t respond in time.

1 Like

I would like to see this as a defaulted OptionSet on the existing sort/sorted method

I agree that it’s a very positive thing for messages not to fall into a void with the passage of time, and it’s very nice that we can pull up a whole thread, no matter how far back, when there’s a reply. However, the goal was to enable more participation that drives the conversation forward, better substantive replies, less context switching overhead, and so on.

The point of my earlier reply is that it’s disappointing when all this powerful new stuff is used to enable “I like this” to be appended to discussions at arbitrary times, which doesn’t drive the conversation forward, has no substance, and pulls the community back to old topics without anything further to contribute.

1 Like

Back then the unstable sort had some issues that meant it reverted to worst-case performance in some common cases. Now that those are fixed, I’d doubt a stable sort could beat it.

1 Like

By that I don’t mean to imply we shouldn’t have a stable sort, just that replacing the extant version outright doesn’t need to be a goal. I think it’d probably be fine if the stable sort was even the default, and you had to opt into the higher performance version.

Sometimes that’s true, but like with containsOnly, sometimes it’s not even implementation holding us back.

In that particular case, I actually thought we already accepted it and was surprised when I couldn’t find it one day. I searched on GitHub, couldn’t find it, so I bumped the thread to revive the discussion. I actually like that it’s so easy to find old topics - it’s better to group discussion in one place rather than scatter it over time. How is somebody new to the forums supposed to catch up on 10+ threads ranging over years?

If a particular issue keeps getting bumped, it’s an indication that the community considers it a priority. Eventually somebody will implement it.

Perhaps your concern could be solved with better moderation? Perhaps not locking the thread per-se, but including a banner on the reply box asking people to avoid “me too”-style comments?

My concern with a banner is that people will eventually stop seeing it.

My preference if we went this route is that, only in the cases an old (3-6 months) thread is bumped, the user is prompted to add to the discussion, and consider summarising it for new readers. A further confirmation box reiterating these points would be helpful, although I’m not sure whether Discourse supports this.

I encourage you to check my post here.

the #warning proposal is a great example of a good idea that got resurrected in this way. even if it derails some threads, swift still moves forward

It is indeed a very good example of how an idea can come back, but it was not resurrected “in this way” if by “this” you mean “bumping.”

In fact, it could not be more different. There, the author incorporated the discussion into a revised proposal and even wrote the implementation, then returned to the list with the result. That is the ultimate moving forward, and the diametrical opposite of writing, “I like this. Can we have it?”

2 Likes

I think it’d probably be fine if the stable sort was even the default, and you had to opt into the higher performance version.

I agree. My preferred solution would be to convert the existing sort to be stable would be the best move, and to introduce sortUnstably (not great naming I know but I’d really prefer it start with the word “sort”). This would be in keeping with the choice most other languages have made.

Adding sortUnstably and adding a stability guarantee to the existing definition would need an evolution proposal, but re-implementing the existing sort to be stable instead of unstable wouldn’t, necessarily, since it’s just an implementation detail, so long as we can keep to the current complexity guarantee. There’s good reason to believe this re-implementation could be a performance improvement in some cases even when switching to a stable sort. I’ve opened a thread over on the std lib dev forum to discuss the implementation.

5 Likes