# Add stable sort algorithm **URL:** \ **Category:** Discussion\ **Created:** [December 25, 2015, 12:20pm UTC](https://forums.swift.org/t/add-stable-sort-algorithm/778 "2015-12-25T12:20:50Z")\ **Posts on this page:** 16\ **Page:** 1
**Author:** ![Arsen\_Gasparyan](https://avatars.discourse-cdn.com/v4/letter/a/35a633/32.png) [@Arsen\_Gasparyan](https://forums.swift.org/u/Arsen_Gasparyan)\ **Post date:** [December 25, 2015, 12:20pm UTC](https://forums.swift.org/t/add-stable-sort-algorithm/778/1 "2015-12-25T12:20:50Z")
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 ---
**Author:** ![masters3d](https://avatars.discourse-cdn.com/v4/letter/m/c4cdca/32.png) [@masters3d](https://forums.swift.org/u/masters3d)\ **Post date:** [January 24, 2018, 10:00pm UTC](https://forums.swift.org/t/add-stable-sort-algorithm/778/2 "2018-01-24T22:00:09Z")
I am in favor of this. > > > | | | > |------------------|-----------------|… > |Previous ID | SR-306 | > |Radar | rdar://problem/18221680 | > |Original Reporter | @gribozavr | > |Type | Improvement | > > \ > \Additional Detail from JIRA\ > > | | | > |------------------|-----------------| > |Votes | 5 | > |Component/s | Standard Library | > |Labels | Improvement, NewAPIRequest, StarterBug, StarterProposal | > |Assignee | None | > |Priority | Medium | > > > > md5: 37f09a79466d145bd076877be8089150 > > \ > > > > > > \*\*Issue Description:\*\* > > > 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. A solution is to drop to Objective-C, [https://medium.com/@topLayoutGuide/a-swift-sorting-problem-e0ebfc4e46d4](https://medium.com/@topLayoutGuide/a-swift-sorting-problem-e0ebfc4e46d4) ---
**Author:** ![Jon\_Shier](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/jon_shier/32/921_2.png) [@Jon\_Shier](https://forums.swift.org/u/Jon_Shier)\ **Post date:** [January 24, 2018, 10:15pm UTC](https://forums.swift.org/t/add-stable-sort-algorithm/778/3 "2018-01-24T22:15:13Z")
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. ---
**Author:** ![taylorswift](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/taylorswift/32/43413_2.png) [@taylorswift](https://forums.swift.org/u/taylorswift)\ **Post date:** [January 24, 2018, 10:38pm UTC](https://forums.swift.org/t/add-stable-sort-algorithm/778/4 "2018-01-24T22:38:00Z")
smfh they didn’t even get the meme right ---
**Author:** ![taylorswift](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/taylorswift/32/43413_2.png) [@taylorswift](https://forums.swift.org/u/taylorswift)\ **Post date:** [January 24, 2018, 10:40pm UTC](https://forums.swift.org/t/add-stable-sort-algorithm/778/5 "2018-01-24T22:40:50Z")
you can stable sort anything by enumerating it and sorting lexicographically. ---
**Author:** ![xwu](https://avatars.discourse-cdn.com/v4/letter/x/b487fb/32.png) [@xwu](https://forums.swift.org/u/xwu)\ **Post date:** [January 24, 2018, 11:13pm UTC](https://forums.swift.org/t/add-stable-sort-algorithm/778/6 "2018-01-24T23:13:07Z")
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. ---
**Author:** ![taylorswift](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/taylorswift/32/43413_2.png) [@taylorswift](https://forums.swift.org/u/taylorswift)\ **Post date:** [January 24, 2018, 11:28pm UTC](https://forums.swift.org/t/add-stable-sort-algorithm/778/7 "2018-01-24T23:28:03Z")
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. ---
**Author:** ![AlexanderM](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/alexanderm/32/9781_2.png) [@AlexanderM](https://forums.swift.org/u/AlexanderM)\ **Post date:** [January 24, 2018, 11:29pm UTC](https://forums.swift.org/t/add-stable-sort-algorithm/778/8 "2018-01-24T23:29:08Z")
I would like to see this as a defaulted OptionSet on the existing sort/sorted method ---
**Author:** ![xwu](https://avatars.discourse-cdn.com/v4/letter/x/b487fb/32.png) [@xwu](https://forums.swift.org/u/xwu)\ **Post date:** [January 25, 2018, 12:34am UTC](https://forums.swift.org/t/add-stable-sort-algorithm/778/9 "2018-01-25T00:34:38Z")
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. ---
**Author:** ![nnnnnnnn](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/nnnnnnnn/32/264_2.png) [@nnnnnnnn](https://forums.swift.org/u/nnnnnnnn)\ **Post date:** [January 25, 2018, 1:11am UTC](https://forums.swift.org/t/add-stable-sort-algorithm/778/10 "2018-01-25T01:11:07Z")
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. ---
**Author:** ![nnnnnnnn](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/nnnnnnnn/32/264_2.png) [@nnnnnnnn](https://forums.swift.org/u/nnnnnnnn)\ **Post date:** [January 25, 2018, 1:19am UTC](https://forums.swift.org/t/add-stable-sort-algorithm/778/11 "2018-01-25T01:19:42Z")
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. ---
**Author:** ![Karl](https://avatars.discourse-cdn.com/v4/letter/k/34f0e0/32.png) [@Karl](https://forums.swift.org/u/Karl)\ **Post date:** [January 25, 2018, 2:39pm UTC](https://forums.swift.org/t/add-stable-sort-algorithm/778/12 "2018-01-25T14:39:01Z")
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? ---
**Author:** ![MutatingFunk](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/mutatingfunk/32/984_2.png) [@MutatingFunk](https://forums.swift.org/u/MutatingFunk)\ **Post date:** [January 25, 2018, 2:55pm UTC](https://forums.swift.org/t/add-stable-sort-algorithm/778/13 "2018-01-25T14:55:17Z")
> [@Karl](#): > > 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](https://forums.swift.org/t/auto-lock-old-evolution-threads/8845). ---
**Author:** ![taylorswift](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/taylorswift/32/43413_2.png) [@taylorswift](https://forums.swift.org/u/taylorswift)\ **Post date:** [January 25, 2018, 9:06pm UTC](https://forums.swift.org/t/add-stable-sort-algorithm/778/14 "2018-01-25T21:06:50Z")
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 ---
**Author:** ![xwu](https://avatars.discourse-cdn.com/v4/letter/x/b487fb/32.png) [@xwu](https://forums.swift.org/u/xwu)\ **Post date:** [January 25, 2018, 11:00pm UTC](https://forums.swift.org/t/add-stable-sort-algorithm/778/15 "2018-01-25T23:00:34Z")
> [@taylorswift](#): > > the #warning proposal is a great example of a good idea that got resurrected in this way. 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?" ---
**Author:** ![ben-cohen](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/ben-cohen/32/296_2.png) [@ben-cohen](https://forums.swift.org/u/ben-cohen)\ **Post date:** [January 26, 2018, 11:04am UTC](https://forums.swift.org/t/add-stable-sort-algorithm/778/16 "2018-01-26T11:04:00Z")
> 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](https://forums.swift.org/t/revisiting-the-choice-of-sort-algorithm/8958) over on the std lib dev forum to discuss the implementation.