Is the goal to provide API separately like stableSort[InPlace](), or to have optional parameters on the existing functions, like sort[InPlace](stable: true)?

That would be a good point to discuss on swift-evolution.

Comment by Félix Fischer (JIRA)

Is this dropped? It looks dropped.

I could take this one... if you guys don't mind and still consider it helpful 🙂

Although... it probably needs to pass through swift-evolution first. Hmm...

Also, this is for the StdLib, so someone has already probably implemented a good and stable algorithm in the way that would be needed. After all, it's Swift. People have done many things already with it xD

Comment by Raphael (JIRA)

@gribozavr I hope you're not advocating for Insertion Sort as general-purpose sorting algorithm!

Comment by Félix Fischer (JIRA)

He probably isn't XD

Also, we could probably use something like this. That way, we'd base the stable sort in the already-tested, fast af Sort in the StdLib, without losing much performance or fiddliness.|https://stackoverflow.com/questions/1427608/fast-stable-sorting-algorithm-implementation-in-javascript].]

I'm gonna check the source code, and if this is possible, I'll send an email to Swift Evolution

Comment by Raphael (JIRA)

felix91gr (JIRA User) Copying arrays an additional two times? Hm. Why not just use good old Mergesort? There are also in-place stable sorting algorithms. Nothing new to invent.

Comment by Félix Fischer (JIRA)

Because Quicksort (and in general, any algorithm that uses it) is very good at using the cache. How are the Block Sorts in this regard? If they are comparable, marvelous: they should be included in the StdLib. But if they aren’t, like HeapSort, I’d consider another approach, even if it took O👎 extra memory to be run.

Comment by Raphael (JIRA)

True, Quicksort is that. As these things go, we'll have to pay something for stability. You seem to be saying, "let's only include such an algorithm if it's as fast as the unstable sort"; I don't think a solution lies that way.

I have not looked into it in depth, but my gut feeling is that bottom-up Mergesort should be reasonably cache-efficient. Maybe the trickery to make it work in-place hurts this, I'm not sure. Research literature on this exists (of course), but I don't have the time to dig through it.

Why would you expect extra memory use to improve cache efficiency? Seems unlikely to me: "new" memory will always provoke cache misses.

Proposal: SE-0372