quadsort

简介------

本文介绍了一种稳定的自底向上自适应无分支合并排序算法,名为quadsort。底部提供了可视化和基准测试。

quad swap 分析器---------------------- quadsort 以一个分析器开始,其任务如下:

1. 使用最少比较来检测有序数据。
2. 使用最少比较来检测倒序数据。
3. 在对随机数据进行处理时,完成上述任务而不影响性能。
4. 使用 8 个元素的已排序块退出 quad swap 分析器。

有序数据处理 ----------------------- Quadsort 的分析器一次处理 8 个元素。它对 (1,2)、(3,4)、(5,6) 和 (7,8) 这 4 对元素进行 4 次比较，结果被存储，并创建一个位掩码，其值介于 0 和 15 之间，用于表示所有可能的组合。如果结果为 0，则表示这 4 次比较都有序。

剩下的就是在元素 (2,3)、(4,5) 和 (6,7) 上进行 3 次比较,以确定 8 个元素是否有序。传统的排序算法会进行 7 次分支式的单元比较,平均情况下会导致 3.2 次分支误判。使用 quadsort 的方法平均情况下会导致 0.2 次分支误判。如果数据有序,quadsort 会继续处理下一个 8 个元素。如果数据既不有序也不反序,将使用存储的比较结果执行 4 次无分支交换,然后是无分支奇偶合并。稍后会详细介绍这点。

逆序处理---------------------- 通常使用简单的反转函数来移动逆序数据,如下所示。