有没有比快速排序和时间排序更快的排序算法？

在数组不能被4完全除以的情况下，存在1-3个元素的尾部使用传统的交换进行排序。

在四次排序的第一阶段，使用四元组交换将数组预排序为如上所述的已排序的4元素块。

第二阶段使用类似于四元交换的方法来检测正序和逆序排列，但是由于它是由4个、16个、64个或更多元素组成的排序块，所以最后一步需要像传统的合并排序一样进行处理。

在第一行中，四元组交换用于创建4个块，每个块包含4个排序元素。在第二行中，使用Quad Merge将块合并成2个块，每个块8个排序的元素，每个块位于交换存储器中。在最后一行，这些块被合并回主内存，我们只剩下1块16个排序的元素。以下是可视化效果。

这些操作确实需要将交换空间的内存开销增加一倍。稍后将详细介绍这一点。

另一个不同之处在于，由于合并操作的成本增加，检查这4个块是按顺序还是按相反顺序是有益的。

在4个块按顺序排列的情况下，跳过合并操作，因为这将是毫无意义的。但是，这确实需要额外的IF检查，并且对于随机排序的数据，如果随着块大小的增加，CHECK变得越来越不可能为True，则需要此检查。幸运的是，这种IF校验的频率是每个环路的四分之一，而潜在的好处是每个环路的四倍。

在4个块处于相反顺序的情况下，执行就地稳定交换。

在4个块中只有2个是按顺序或逆序的情况下，合并本身中的比较是不必要的，并且随后被省略。仍然需要将数据复制到交换存储器，但这是计算密集度较低的过程。

这允许QuadSort使用n个比较而不是n*logn个比较按顺序和逆序序列排序。

传统合并排序的另一个问题是执行浪费的边界检查。这看起来如下所示：

WHILE(a<；=a_max&；&；b<；=b_max)IF(a<；=b)[INSERT a++]ELSE[INSERT b++]。

为了优化这个四重排序，将序列A的最后一个元素与序列B的最后一个元素进行比较。如果序列A的最后一个元素小于序列B的最后一个元素，我们知道(b<；b_max)IF CHECK将始终为假，因为序列A将首先被完全合并。

类似地，如果序列A的最后一个元素大于序列B的最后一个元素，我们知道(a<；a_max)IF CHECK将始终为假。如下所示：

If(val[a_max]<；=val[b_max])WHILE(a<；=a_max){WHILE(a&>；b)[INSERT b++][INSERT a++]}ELSE WHILE(b<；=b){WHILE(a<；=b)[INSERT a++][INSERT b++]}。

当对包含65个元素的数组进行排序时，最终得到一个包含64个元素的已排序数组和一个包含1个元素的已排序数组。由于跳转的能力，如果整个序列是有序的，这将不会导致额外的交换操作。无论如何，如果程序按时间间隔排序，它应该选择一个最佳的数组大小(64、256或1024)来执行此操作。

另一个问题是，次优阵列会导致浪费的交换。要解决这两个问题，当块大小达到数组大小的1/8时，将中止四元合并例程，并使用尾部合并对数组的其余部分进行排序。

尾部合并的主要优点是，它允许将四级排序的交换空间减少到n/2，而不会显著影响性能。

因为QuadSort使用n/2交换内存，所以它的缓存利用率不如就地排序理想。然而，随机数据的就地排序会导致次优交换。根据我的基准测试，对于不耗尽L1缓存(在现代处理器上可以高达64KB)的数组大小而言，QUDSORT似乎总是比就地排序更快。

WolfSort是一种混合基数排序/四次排序，可以提高随机数据的性能。它主要是一个概念证明，只适用于无符号32位和64位整数。

在下面的可视化中，执行了四个测试。第一个检验是关于随机分布的，第二个是关于上升分布的，第三个是关于下降分布的，第四个是关于具有随机尾巴的上升分布的。

上半部分显示交换内存，下半部分显示主内存。颜色用于区分跳过、交换、合并和复制操作。

下面的基准测试是在WSL GCC版本7.4.0(Ubuntu7.4.0-1ubuntu1~18.04.1)上进行的，源代码是用g++-O3 quigadert.cpp编译的。每个测试都运行了100次，并且只报告了最好的运行。

应该注意的是，pdq排序不是一种稳定的排序，这就是它在一般订单数据上速度更快的原因。下面的基准测试是在WSL GCC版本7.4.0(Ubuntu7.4.0-1ubuntu1~18.04.1)上进行的。源代码是使用g++-O3 quigadert.cpp编译的。每个测试都运行了100次，并且只报告了最好的运行。它测量阵列大小从675到100,000的性能。

下面的基准测试是在无线用户线GCC 7.4.0(Ubuntu7.4.0-1ubuntu1~18.04.1)上进行的，源代码是用GCC-O3的quadagelt.c编译的。每个测试都运行了100次，并且只报告了最好的运行。

四次排序：在0.092399秒内对1000000个i32进行了排序。MO：19305366(随机顺序)QSORT：在0.103581秒内排序了1000000个i32。MO：18673007(随机顺序)四次排序：在0.002191秒内排序了1000000个i32。MO：999999(升序)QSORT：在0.026788秒内排序了1000000个i32。MO：9884992(升序)四次排序：在0.013560秒内排序了1000000个i32。MO：4008160(升锯)QSORT：在0.034882秒内排序了1000000个i32。MO：10884985(升锯)四分拣：在0.057610秒内分选了1000000个i32。MO：19241914(通用顺序)QSORT：在0.070901秒内排序了1000000个i32。MO：18617580(通用顺序)四次排序：在0.001780秒内排序了1000000个i32。MO：999999(降序)QSORT：在0.026404秒内排序了1000000个i32。MO：10066432(降序)四次排序：在0.015482秒内排序1000000个i32。MO：9519209(降锯)QSORT：在0.034839秒内排序了1000000个i32。MO：13906008(降锯)四分拣：在0.026516秒内分选了1000000个i32。MO：6786305(随机尾巴)QSORT：在0.046344秒内排序了1000000个i32。MO：12248243(随机尾巴)四次排序：在0.050595秒内排序了1000000个i32。MO：11381790(随机一半)QSORT：在0.067199秒内排序了1000000个i32。MO：14528949(随机半)四次排序：在0.024795秒内排序了1000000个i32。MO：15328606(波序)QSORT：在0.035221秒内排序了1000000个i32。MO：14656080(波序)四次排序：在0.024867秒内排序了1000000个i32。MO：15328606(稳定)QSORT：在0.035251秒内排序了1000000个i32。Mo：14656080(稳定)四分类：在0.013662秒内分类了1023i32s。(随机1-1023)q排序：在0.025581秒内对1023i32进行排序。(随机1-1023)。

在上面的基准测试中，使用相同的通用接口与glibc qort()进行了比较，并且没有任何已知的不公平优势，如内联。

随机顺序：635,202，47,229等升序：1，2，3，4等统一顺序：1，1，1，1，1等降序：999,998,997,996等波形顺序：100，1,102，2,103，3，ETC稳定/不稳定：100，1,102，1,103，1，等随机范围：对包含随机数据的1000个大小从0到999的数组进行排序的时间。

这个特殊的测试是使用Cygwin的qort()实现执行的，该实现在幕后使用快速排序。源代码是用GCC-O3quadagedt.c编写的。每个测试都运行了100次，并且只报告了最好的运行。

四次排序：在0.119437秒内对1000000个i32进行了排序。MO：19308657(随机顺序)QSORT：在0.133077秒内排序了1000000个i32。MO：21083741(随机顺序)四次排序：在0.002071秒内排序了1000000个i32。MO：999999(升序)QSORT：在0.007265秒内排序了1000000个i32。MO：3000004(升序)四次排序：在0.019239秒内排序了1000000个i32。MO：4007580(升锯)QSORT：在0.071322秒内排序了1000000个i32。MO：20665677(升锯)四分拣：在0.076605秒内分选了1000000个i32。MO：19242642(通用顺序)QSORT：在0.038389秒内排序了1000000个i32。MO：6221917(通用顺序)四次排序：在0.002305秒内排序了1000000个i32。MO：999999(降序)QSORT：在0.009659秒内排序了1000000个i32。MO：4000015(降序)四次排序：在0.022940秒内排序1000000个i32。MO：9519209(降锯)QSORT：在0.042135秒内排序了1000000个i32。MO：13152042(降锯)四分拣：在0.034456秒内分选了1000000个i32。MO：6787656(随机尾巴)QSORT：在0.098691秒内排序了1000000个i32。MO：20584424(随机尾巴)四次排序：在0.066240秒内排序了1000000个i32。MO：11383441(随机一半)QSORT：在0.118086秒内排序了1000000个i32。MO：20572142(随机半)四次排序：在0.038116秒内排序了1000000个i32。MO：15328606(波序)QSORT：在4.471858秒内排序了1000000个i32。MO：1974047339(波序)四次排序：在0.060989秒内排序了1000000个i32。MO：15328606(稳定)QSORT：在0.043175秒内排序了1000000个i32。MO：10333679(不稳定)四排序：在0.016126秒内排序1023i32。(随机1-1023)q排序：在0.033132秒内对1023i32进行排序。(随机1-1023)。

在这个基准测试中，很清楚为什么快速排序通常比传统合并排序更受欢迎，因为它对升序、统一和降序数据的比较较少。然而，在大多数测试中，它的性能都比Quadort差。快速排序对波序数据的排序速度也非常慢，随机范围测试表明，在对小数组进行排序时，QuickSort的速度是QuadSort的两倍多。

快速排序在泛型和稳定测试中速度更快，但这只是因为它不稳定。