Use grailsort for sort_unstable

[MusicTheorist]

Hello, Rust contributors!

I've been managing a bit of a passion project centered around Grailsort, a stable, in-place, O(n log n) worst-case sorting algorithm, for a while now. It was partially inspired by previous issues brought up in this repo, including #19221 and
rust-lang/rfcs#956 (comment).

Our project is currently focusing on rewriting and documenting Grailsort, with the hopes of making the algorithm much more readable and intuitive.

I was curious if there's still interest in implementing an in-place sort like this for Rust, especially because one of our contributors is maintaining a WIP Rust version of said rewrite in our repo.

https://github.com/MusicTheorist/Rewritten-Grailsort

Feel free to let us know what your thoughts are. Thanks for reading!

[jyn514]

Can you explain the difference between Grailsort and the current slice::sort_unstable algorithm?

[666666t]

The current slice::sort_unstable is based off a variant of Pattern-Defeating Quicksort (PDQsort), which generally achieves a high performance in O(n log n) time, and is in-place (non-allocating), however is unstable as the name implies, meaning values which respond as equal within the bounds of the Eq trait may be re-ordered, which is generally undesirable and the reason why slice::sort exists.

slice::sort is based in Timsort, a particularly adaptive version of merge sort which is fairly quick, maintains O(n log n) time, and is stable, ensuring elements that are equal by whatever comparison metric is provided are not rearranged. However, it does use allocations, requiring O(n) extra space in the form of temporary storage half the size of the given slice, meaning it is out-of-place.

Block merge sorts, such as Grailsort (and certain WIP derivative projects), in contrast, Balance the conditions of the prior 2 sorts, producing a sort that maintains fair performance in O(n log n) time, maintains stability between values, and can be executed in-place, with zero additional allocations for buffers or extra space.

tl;dr: slice::sort_unstable is in-place and O(n log n), but is unstable, meaning values which compare equally may change order.
slice::sort is stable and O(n log n), but out-of-place, meaning it must allocate additional data (in this case half the slice's original size) in the process.
Grailsort is stable, O(n log n), and in-place, satisfying all 3 of the general conditions for such sorts while still maintaining fair performance.

[Gaming32]

@666666t By “certain WIP derivative projects,” you mean Holy Grailsort? (there’s also Kota, Ecta, and Helium)

[666666t]

By “certain WIP derivative projects,” you mean Holy Grailsort? (there’s also Kota, Ecta, and Helium)

Correct, though given the original focus of this issue cites Grailsort in particular, It seemed preferable to keep the focus on that, while Holy Grailsort and similar WIP projects seek to improve adaptability and certain other aspects but generally don't appear as complete as the current Grailsort rewrites.

[666666t]

Regardless, as for a generic run-down of the algorithm itself;

Grailsort works by maintaining an in-place buffer of unique values which are collected from the slice at the beginning, generally of some power of 2 size which scales with sqrt(n). It uses this in-place buffer (which is guaranteed to be stable by only collecting unique values) to traverse the array, performing in-place merges with the provided space. For fragments which are small enough to be merged, it does this outright, in one piece. For fragments which are larger than the available in-place buffer, the fragments are merged in "blocks", using a method of dividing the merge operation which involves "tagging" of blocks and fragments to ensure stability. After all fragments are merged, the in-place buffer is re-inserted to the slice, using a method of block rotations for quick insertion.

I'm certainly not the most versed in explaining the algorithm as a whole, but that should give a short idea of how the parts of the algorithm function in theory.

[666666t]

Ah, sorry, I should make it clear for noting;

Grailsort is a stable sort, in-line with slice::sort, but is in-place, requiring no extra allocations, unlike the existing implementation. slice::sort_unstable is in-place, but it lacks the stability guarantee of slice::sort or Grailsort, which puts block merge sorts "in between" the two, more akin to something like a slice::sort_inplace type method, with the stability guarantees of slice::sort and in-place nature of slice::sort_unstable, at the cost of some speed (while still remaining in O(n log n) time, however).

[MusicTheorist]

Right, definitely want to make clear Grailsort is a stable sort. It's not unstable.

[scottmcm]

How does its speed compare to slice::sort?

[MusicTheorist]

@scottmcm While Grailsort has a solid design to it, there are many flaws and opportunities to micro-optimize which generally make a "vanilla" implementation slower than Timsort.

Generally speaking, I would characterize Grailsort as decently cache-friendly due to relatively simple linear memory accesses while also scaling pretty favorably. According to the original author, comparisons are ~1.6 * n log n and writes are ~2.1 * n log n in the worst-case.

Grailsort is nowhere near as adaptive as Timsort, and in fact we're pretty sure its best case is O(n log n).

For what it is, I think it's pretty clever and impressive but it definitely has some kinks that need to be ironed out. Our plans for an optimized Grailsort yield an algorithm that is at least 15-30% faster on average.

[the8472]

Is the issue title correct? Would you intend to replace the stable or the unstable sort implementation?

[nagisa]

is generally undesirable and the reason why slice::sort exists.

Its the other way around. The slice::sort_unstable has been added because people felt the potential performance increase with an unstable sort is worth the extra API surface over slice::sort. The desirable properties for the sort_unstable are in-place first and speed second. If the unstable_sort is replaced with a slower algorithm that's stable, then the API loses half of its intended purpose.

That said I'd welcome improvements to the stable slice::sort if there are any to be had.

[MusicTheorist]

@the8472 My bad for not being clear enough, I wasn't aiming to necessarily replace any functions in Rust. I was asking if people still were interested in a non-allocating sort.

[666666t]

(Or at least, a non-allocating stable sort, in this case.)

[ecstatic-morse]

I wrote an in-depth explanation of the Huang and Langston-style block sort (grailsort) as well as a Rust implementation. Perhaps this will help potential reviewers to understand the block sort paradigm. I looked at some of the implementations in the Rewritten Grailsort project, but it didn't seem to close the documentation gap between grailsort and "wikisort". In the process, I was able to implement the block tagging scheme described by Huang and Langston, although I'm not sure if halving the size of the internal buffer is actually worth the extra bookkeeping.

Personally, I would not recommend we switch sort to a block sort given the complexity and overhead compared to merge sort. The addition of a version of std that propagated allocation errors or a compelling use for a stable sort in no_std environments might change my mind though, and it would be nice to have a standard-library quality implementation on crates.io.

[Enselic]

Triage: Thank you for reporting. Always interesting to learn about new sorting algorithms.

While Grailsort has a solid design to it, there are many flaws and opportunities to micro-optimize which generally make a "vanilla" implementation slower than Timsort.

Then let's close this issue for now, but feel free to reopen when the Grailsort implementation outperforms what Rust currently has!