Glidesort 的 Rust 实现,这是我的稳定的自适应快速排序/归并排序混合排序算法。
Glidesort 是一种新的稳定排序算法,它将 Timsort 式合并排序对预先排序的数据的最佳情况行为,以及 打败模式的快速排序 对具有许多重复值的数据的最佳情况行为相结合。它是一种基于比较的排序算法,支持任意比较运算符,对于具有模式的数据,它具有出色的性能,但对于随机数据也非常快速。
Glidesort 可以使用尽可能多的(最多为 n)或尽可能少的额外内存,您可以根据需要选择。如果只提供 O(1) 内存,则平均和最坏情况将为 O(n (log n)^2),但是在实际应用中,对于除最不均衡的数据大小/辅助空间比例外,其性能都非常好。默认情况下,它会分配最多 n 个元素的数据,除非超过 1 MiB,在这种情况下,我们将其缩小为 n / 2 个元素的数据,直到 1 GiB 之后,glidesort 才会使用 n / 8 内存。
性能因机器和数据集而异，因此您的使用情况也会有所不同。尽管如此，以下是来自 2021 年 Apple M1 机器的一个示例基准，比较了 u64 的不同输入分布下的 [T]::sort 和 [T]::sort_unstable：
glidesort::sort_with_buffer(&mut a, buf) 要求您传递一个 &mut [MaybeUninit<T>] 缓冲区,它将(独占性地) 使用此缓冲区作为辅助空间来排序元素。glidesort::sort_in_vec(&mut v) 的行为与普通 glidesort 相同,但它会在传入的 Vec<T> 结尾分配辅助空间。这允许未来的排序调用重复使用同一个空间,从而减少分配。这两个族群还支持 _by 和 _by_key 接口。
暂无开放 Issues，或尚未同步最近议题。