Fluxsort：一种稳定的自适应分区比较排序

本文档描述了一种名为fluxsort 的基于分区稳定自适应比较的排序。底部提供基准和可视化。 Fluxsort 从一个分析器开始，该分析器检测完全排序的数组并使用 n 次比较对逆序数组进行排序。如果数组的随机性小于 25%，它还可以获得预排序的度量并切换到四边排序。分区以类似于快速排序的自上而下的方式执行。 Fluxsort 为小于 1024 个元素的分区获得 9 的伪中值，否则获得 15 的伪中值。获得的中值元素将被称为枢轴。小于 24 个元素的分区使用四元排序进行排序。获得枢轴后，数组从头到尾解析。小于枢轴的元素被原地复制到数组的开头，大于枢轴的元素被复制到交换内存。分区例程在主内存和交换内存中的两个分区上递归调用。通过 ptx 指针通过交换和主内存进行递归分区，尽管实现起来很简单，但它可能是一种新技术，因为其背后的逻辑有点脑筋急转弯。为了避免失控递归，如果一个分区小于另一个分区大小的 1/16，则两个分区的通量排序都会切换到四边形排序。在随机唯一值的分布中，9 的伪中位数和 15 的伪中位数的误报概率为 65,536 分之一，15 的伪中位数为 16,777,216 分之一。过早触发四分排序的使用，导致性能下降 2 倍。

Fluxsort 使用无分支比较优化，类似于 Stefan Edelkamp 和 Armin Weiss 在“BlockQuicksort：分支错误预测如何不影响快速排序”中描述的方法。中值选择使用一种新颖的无分支比较技术，该技术使用 8 到 12 次（平均 10.66）比较选择 9 的伪中值，使用 14 到 25 次（平均 21.33 次）比较选择 15 的伪中值。当比较本身是分支的并且最大的性能提升是在 32 位和 64 位整数上时，这些优化效果不佳。 Fluxsort 分配交换内存的 n 个元素，与 quadsort 共享。递归需要 log n 堆栈内存。 Fluxsort 的 C 实现支持长双精度和 8、16、32 和 64 位数据类型。通过使用指针，可以对任何其他数据类型进行排序，例如字符串。 ┌────────────────────────┐┌──────────────────────────┐ │比较││交换内存│ ┌───────────────┐├────────┬────────┬────────┤├ ────────┬───────┬─────────┤┌──────┐┌──────────┐┌────── ───┐ │name ││min │avg │max ││min │avg │max ││stable││partition││自适应│ ├──────────────┤├── ──────┼────────┼──────────┤├────────┼────────┼────────┤├── ────┤├─────────┤├─────────┤ │fluxsort ││n │n log n│n log n││1 │n │n ││yes ││是││是│ ├─────────────────┤├───────┼────────┼────────┤├ ────────┼───────┼──────────┤├──────┤├──────────┤├────── ───┤ │quadsort ││n │n log n│n log n││1 │n │n ││yes ││ no ││yes │ ├────────────────── ┤├───────┼─────────┼───────┤├───────┼────────┼────────── ┤├──────┤├──────────┤├─────────┤ │quicksort ││n │n log n│n² ││1 │1 │1 │ │ 否 ││是 │ │ 否 │ ├───────────────┤├───────┼────────┼────────── ┤├───────┼─────────┼─────────┤├──────┤├──────────┤├──── ──────┤ │introsort ││n log n│n log n│n log n││1 │1 │1 ││ 否 ││是 ││ 否 │ └──────────── ────┘└────────┴───────┴────────┘└────────┴────────┴──── ────┘└──────┘└──────────┘└──────────┘ 想要p的人ort fluxsort 可能想看看 twinsort，它是quadsort的简化实现。 Fluxsort 本身比较简单。

在下面的可视化中，对 512 个元素执行了四个测试：随机、通用、随机半块和升序瓷砖。大于 48 个元素的分区使用 15 的伪中值来选择枢轴。以下基准测试是在 WSL gcc 7.5.0 版（Ubuntu 7.5.0-3ubuntu1~18.04）上使用 wolfsort 基准测试进行的。源代码是使用 g++ -O3 -w -fpermissive bench.c 编译的。条形图显示了 100,000 个 32 位整数上 100 个的最佳运行。对fluxsort 和std::stable_sort 的比较是内联的。以下基准测试是在 WSL gcc 7.4.0 版（Ubuntu 7.4.0-1ubuntu1~18.04.1）上进行的。源代码是使用 gcc -O3 bench.c 编译的。条形图显示了 100,000 个 32 位整数上 100 个的最佳运行。通量排序和 qsort 的比较不是内联的。基准测试中的 stdlib qsort() 是一个归并排序变体。