Glidesort

Glidesort is a novel stable sorting algorithm that combines the best-case behavior of Timsort-style merge sorts for pre-sorted data with the best-case behavior of pattern-defeating quicksort for data with many duplicates. It is a comparison-based sort supporting arbitrary comparison operators, and while exceptional on data with patterns it is also very fast for random data.

For sorting n elements with k distinct values glidesort has the following characteristics by default:

Best    Average     Worst       Memory      Stable      Deterministic
n       n log k     n log n     n / 8       Yes         Yes

Glidesort can use as much (up to n) or as little extra memory as you want. If given only O(1) memory the average and worst case become O(n (log n)^2), however in practice its performance is great for all but the most skewed data size / auxiliary space ratios. The default is to allocate up to n elements worth of data, unless this exceeds 1 MiB, in which case we scale this down to n / 2 elements worth of data up until 1 GiB after which glidesort uses n / 8 memory.

Benchmark

Performance varies a lot from machine to machine and dataset to dataset, so your mileage will vary. Nevertheless, an example benchmark from a 2021 Apple M1 machine comparing against [T]::sort and [T]::sort_unstable for various input distributions of u64:

Compiled with rustc 1.69.0-nightly (11d96b593) using --release --features unstable and lto = "thin".

Usage

Use cargo add glidesort and replace a.sort() with glidesort::sort(&mut a). A similar process works for sort_by and sort_by_key.

Glidesort exposes two more families of sorting functions. glidesort::sort_with_buffer(&mut a, buf) asks you to pass a &mut [MaybeUninit<T>] buffer which it will then (exclusively) use as auxiliary space to sort the elements. glidesort::sort_in_vec(&mut v) behaves like normal glidesort but will allocate its auxiliary space at the end of the passed Vec<T>. This allows future sorting calls to re-use the same space and reduce allocations. Both these families also support the _by and _by_key interface.

Visualization

This visualization focuses on demonstrating the advanced merging techniques in glidesort:

https://user-images.githubusercontent.com/202547/216675278-e4c8f15c-e42d-4224-b8c7-fdc67fdc2bde.mp4

This visualization shows how glidesort is adaptive to both pre-existing runs as well as many duplicates together:

https://user-images.githubusercontent.com/202547/216675274-6e61689f-a120-4b7c-b1a7-9b5aa5fd013e.mp4

Note that both visualizations have different small sorting thresholds and auxiliary memory parameters to show the techniques in action on a smaller scale.

Technique overview

Glidesort uses a novel main loop based on powersort. Powersort is similar to Timsort, using heuristics to find a good order of stably merging sorted runs. Like powersort it does a linear scan over the input, recognizing any ascending or strictly descending sequences. However, unlike powersort it does not eagerly sort sequences that are considered unordered into small sorted blocks. Instead it processes them as-is, unsorted. This process produces logical runs, which may be sorted or unsorted.

Glidesort repeatedly uses a logical merge operation on these logical runs, as powersort would. In a logical merge unsorted runs are simply concatenated into larger unsorted runs. Sorted runs are also concatenated into double sorted runs. Only when merging a sorted and unsorted run finally the unsorted run is sorted using stable quicksort, and when merging double sorted runs glidesort uses interleaved ping-pong merges.

Using this novel hybrid approach glidesort can take advantage of arbitrary sorted runs in the data as well as process data with many duplicate items faster similar to pattern-defeating quicksort.

Stable merging

Glidesort merges multiple sorted runs at the same time, and interleaves their merging loops for better memory-level and instruction-level parallelism as well as hiding data dependencies. For similar reasons it also interleaves independent left-to-right and right-to-left merging loops as bidirectional merges, which are a generalization of quadsorts parity merges. Merging multiple runs at the same time also lets glidesort use ping-pong merging, avoiding unnecessary memcpy calls by using the implicit copy you get from an out-of-place merge. All merging loops are completely branchless, making it fast for random data as well.

Glidesort further uses binary searches to split up large merge operations into smaller merge operations that it then performs at the same time using instruction-level parallelism. This splitting procedure also allows glidesort to use arbitrarily small amounts of memory, as it can choose to split a merge repeatedly until it fits in our scratch space to process.

Stable quicksort

Yes, stable quicksort. Wikipedia will outright tell you that quicksort is unstable, or at least all efficient implementations are. That simply isn't true, all it needs is auxiliary memory. Credit to Igor van den Hoven's fluxsort for demonstrating that stable quicksort can be efficient in practice.

Glidesort uses a novel bidirectional stable partitioning method that interleaves a left-to-right partition scan with a right-to-left partition scan for greater memory-level parallelism and hiding data dependencies. Partitioning is done entirely branchlessly (if the comparison operator is), giving consistent performance on all data.

License

Glidesort is dual-licensed under the Apache License, Version 2.0 and the MIT license.