WolfSort：一种超高速混合基数排序算法

本文档描述了一种稳定的自适应基数/归并混合排序，名为wolfort。对于随机和有序数据的混合排序，它可能是迄今为止编写的最快的排序。

虽然自适应合并排序在排序有序数据时速度非常快，但它不能有效地进行分区是其最大的弱点。另一方面，基数排序无法利用已排序的数据。WolfSort试图避免每种算法的最坏情况。

WolfSort使用QuadSort作为其自适应合并排序，因为它比TimSort更快。Wolfort使用的基数排序有两个主要函数。

WolfSort的操作类似于典型的基数排序，方法是创建256bucket，并将每个无符号32位整数除以16777216。如果不进行任何优化，这将使内存开销增加256倍。作为一种混合排序，wolfort通过赋予每个存储桶最大大小的1/8来解决这个问题。

如果达到最大存储桶大小，则中止基数排序并运行四次排序。虽然这看起来可能很浪费，但实际上这意味着以相对较小的成本避免了每种算法的最坏情况。

因为此方法相当于就地MSD基数排序，所以在分区完成后，256个存储桶将按顺序排列。下一步是对每个桶的内容进行排序，四次排序就完成了。

对于O(N)分区过程，WolfSort需要交换内存中数组大小的8倍，随后的排序过程需要交换内存中数组大小的1/32。

如果没有足够的内存可用，则wolfort会使用QuadSort，它需要交换内存中阵列大小的1/2。

在理想条件下，分配和释放10MB内存与分配和释放80MB内存在计算上没有差别。从历史上看，软件的内存总是很低的，因此后来开发了排序算法，以便尽可能少地使用额外的内存。如今，大多数现代系统都有几个未使用的、闲置的内存。

在分区过程中，每个桶都变得类似于薛定谔的猫，它可以几乎全部使用，也可以完全不使用，或者介于两者之间。根据概率，我们知道实际使用的恰好是1/8。唯一的开销是跟踪每个桶的大小，并在每次添加时检查桶是否没有溢出。

WolfSort主要是一个概念证明，目前它只正确支持无符号32位整数。

在许多平台上，使用malloc()进行内存分配是一个瓶颈。使用更好的内存分配器或永久交换内存是一种可能的解决方案。

下面的测试是在无线用户线GCC 7.4.0(Ubuntu7.4.0-1ubuntu1~18.04.1)上进行的，源代码使用g++-O3-fpermissive基准进行编译。

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

下图的X轴是元素数，Y轴是执行时间。