Add non-allocating sort function to libcore

[mahkoh]

[veddan]

I have a #[no_std] introsort implementation at veddan/rust-introsort. It's faster than the standard sort for all inputs I can find, and is significantly faster if the input is partially sorted or has few unique values. One temporary issue is that, unlike the merge sort in std, the comparison function fails to inline with old-style closures. Therefore it uses unboxed closures and has a different signature than std's sort_by.

Maybe the non-allocating sort function in core can be re-exported in std as unstable_sort or something similar?

[thestinger]

It would be interesting to try out one of the bleeding edge in-place merge sort algorithms:

• https://github.com/BonzaiThePenguin/WikiSort
• https://github.com/Mrrl/GrailSort

There's no reason not to have high performance, stable sorting and no allocation.

[Gankra]

I started looking into this. GrailSort is a bit faster for some inputs (by the Wikisort author's own claim), but WikiSort is considerably better documented (and public domain!). As such it seems like the more promising algorithm to duplicate.

That said, it's complex. An optimized Wikisort involves an implementation of insertion sort, vanilla merge sort, sorting networks (with side-tables for stability), and of course the actual wikisort algorithm. All in all the impl ends up being about 900 lines of well-documented C++ code. Not insane, but not a walk in the park, either.

[steveklabnik]

I'm pulling a massive triage effort to get us ready for 1.0. As part of this, I'm moving stuff that's wishlist-like to the RFCs repo, as that's where major new things should get discussed/prioritized.

This issue has been moved to the RFCs repo: rust-lang/rfcs#790