基准测试

性能因机器和数据集而异，所以您的性能会有所不同。尽管如此，以下是一个示例基准，它使用2021年苹果M1机器比较了[T]::sort和[T]::sort_unstable对各种输入分布的u64

使用rustc 1.69.0-nightly (11d96b593)和--release --features unstable以及lto = "thin"编译。

使用方法

使用 cargo add glidesort 并将 a.sort() 替换为 glidesort::sort(&mut a)。类似的步骤也适用于 sort_by 和 sort_by_key。

Glidesort 提供了两个额外的排序函数家族。 glidesort::sort_with_buffer(&mut a, buf) 要求您传递一个 &mut [MaybeUninit<T>] 缓冲区，它将（专有地）将其用作辅助空间以对元素进行排序。 glidesort::sort_in_vec(&mut v) 的行为类似于正常的 glidesort，但它将在传递的 Vec<T> 的末尾分配其辅助空间。这允许未来的排序调用重用相同的空间并减少分配。这两个家族也支持 _by 和 _by_key 接口。

可视化

这个可视化侧重于展示 glidesort 中的高级合并技术

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

这个可视化展示了 glidesort 如何适应预存的运行以及许多重复项一起的情况

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

请注意，这两个可视化具有不同的小的排序阈值和辅助内存参数，以展示技术在较小规模上的实际应用。

技术概述

Glidesort 使用基于 powersort 的新型主循环。Powersort 类似于 Timsort，使用启发式算法找到稳定合并排序的运行的良好顺序。与 powersort 类似，它对输入进行线性扫描，识别任何升序或严格降序的序列。然而，与 powersort 不同，它不会急于将考虑为无序的序列排序成小的有序块。相反，它将它们按原样处理，不排序。这个过程产生 逻辑运行，这些运行可能是排序的或不排序的。

Glidesort 重复使用逻辑合并操作对这些逻辑运行，就像 powersort 一样。在逻辑合并中，未排序的运行简单地连接成更大的未排序运行。排序的运行也连接成 双排序 运行。只有当合并排序和未排序运行时，才会使用稳定的快速排序对未排序的运行进行排序，并且当合并双排序运行时，glidesort 使用交错乒乓合并。

使用这种新颖的混合方法，glidesort 可以利用数据中的任意排序运行，并且可以像模式消除快速排序一样更快地处理具有许多重复项的数据。

稳定合并

Glidesort同时合并多个排序好的运行，并交错它们的合并循环，以实现更好的内存级别和指令级别并行性，以及隐藏数据依赖。出于类似原因，它还交错独立的自左向右和自右向左合并循环，作为双向合并，这是quadsort奇偶合并的推广。同时合并多个运行还可以让Glidesort使用乒乓合并，通过使用隐式复制避免不必要的memcpy调用。所有合并循环都是完全无分支的，使其在随机数据上也非常快。

Glidesort进一步使用二分搜索将大型合并操作拆分为较小的合并操作，然后使用指令级别并行性同时执行。这种拆分过程还允许Glidesort使用任意小的内存量，因为它可以选择反复拆分合并，直到它适合我们的临时空间进行处理。

稳定的快速排序

是的，稳定的快速排序。维基百科会直接告诉你快速排序是不稳定的，或者至少所有有效的实现都是。这并不正确，它只需要辅助内存。感谢Igor van den Hoven的fluxsort展示了稳定的快速排序在实践中可以是高效的。

Glidesort使用一种新颖的双向稳定分区方法，它交错进行自左向右和自右向左的分区扫描，以实现更大的内存级别并行性和隐藏数据依赖。分区完全是无分支进行的（如果比较操作符是的话），对所有数据都提供一致的性能。

许可证

Glidesort根据Apache许可证版本2.0和MIT许可证双授权。