Gridsort：比std：sort更快的稳定排序

Gridsort通过将数据存储在简化的二进制多维数据集（多维排序的数组）中对数据进行排序。二进制多维数据集提供了出色的缓存利用率。将二进制多维数据集查看为哈希表是最简单的方法，但它不是使用哈希函数来查找存储桶，而是在查找表上使用二进制搜索。

对元素进行排序时的第一步是无限制的二进制搜索，以查明应在其中存储元素的存储桶。无限二进制搜索的速度比大多数应用程序使用的传统二进制搜索快两倍。一旦找到存储桶，该元素就会添加到存储桶的末尾。

当Gridsort检测到已排序的数据时，它将切换到自适应二进制搜索。

存储桶溢出后，将使用四叉排序对其进行分类并创建一个新存储桶。排序后的数据在两个存储桶之间分配，因此每个存储桶都已装满一半。每个存储桶中最低的元素将添加到查找表中。

将所有元素都插入二进制多维数据集后，每个存储桶都会得到最终排序，并被复制回原始数组。

gridsort的C实现支持长双精度和8、16、32和64位数据类型。通过使用指针，可以对任何其他数据类型进行排序。

┐──────────────────┐┌┐┌────────────────┐ │比较││交换内存│┌─────────────┐├───────────────────┬ ────────┬────────┬────────┤┌────┐┌────────┐┌ ────┐│名称││最小│avg│max││min│avg│max││稳定││分区││自适应│├───────────┤ ──────┼────────┼────────┤├───────┼──────┼────────┤ ──────────────────────┤│gridsort││n│nlogn│nlogn││n│n│n││是││是││是│├─────────────┤├────────┼────────── ────────┼──────┼────┼────────────┤──────────┤ ────┤│合并排序││n日志n│n日志n│n日志n││n│n│n││││否││否│├─────────── ──┤├───────┼───────┼────────┤├───────┼────────┼──── │││n│nlogn│nlogn││1│ n│n││是││否││是│├─────────────┤ ──────────────┼────────────────┤ ──────────┤│快速排序││n│nlogn│n²││1│1│1││否││是││否│├───────── ────┤├──────┼ ──┼────────┤├───────┼──────────────┤ ────┤├──────────────────────────────────────────┤────────────────────────────────────────────────────────────┤ ────────────┘└──────┴────────────────┘└────────┴── ──────┴────────┘└──────┘└────────┘└

当数据完全按顺序排列或按相反顺序排列时，Gridsort会进行n次比较。

想要移植gridsort的人们可能想看看twinsort，这是quadsort的简化实现。 Gridsort本身是cubesort的简化实现。

在下面的可视化中，执行了八项测试。随机，升序，升锯，通用，降序，降锯，随机尾巴和波动顺序。

在下面的可视化中，对随机分布执行一项测试。这种可视化效果更准确地显示了使用指针操作对内存进行分区。

青色数字未排序，绿色数字已排序，白色数字已排序并准备合并，黄色数字是执行二进制搜索以找出要插入下一个数字的位置的索引，洋红色数字已准备好合并回到主数组。

以下基准测试是使用Wolfsort基准测试在WSL gcc版本7.5.0（Ubuntu 7.5.0-3ubuntu1〜18.04）上进行的。源代码是使用g ++ -O3 -w -fpermissive bench.c编译的。条形图显示了32位整数上100的最佳耗尽。内联了gridsort和std :: sort的比较。基准测试中的std :: sort（）应该是就地IntroSort。

以下基准测试是在WSL gcc版本7.4.0（Ubuntu 7.4.0-1ubuntu1〜18.04.1）上进行的。源代码是使用gcc -O3 bench.c编译的。条形图显示了32位整数上100的最佳耗尽。没有内联gridsort和qsort的比较。基准测试中的stdlib qsort（）是mergesort变体。