介绍
本文档介绍了一个名为gridsort的分区稳定的基于自适应比较的排序。
二元立方体
Gridsort通过将数据存储在简化的(多维排序的数组)中对进行排序。 二进制多维数据集提供了出色的缓存利用率。 将二进制多维数据集视为哈希表是最简单的方法,但它不是使用哈希函数来查找存储桶,而是在查找表上使用二进制搜索。
无限二进位搜寻
对元素进行排序的第一步是以查明应在其中存储元素的存储桶。 无限二进制搜索的速度比大多数应用程序使用的传统二进制搜索快两倍。 一旦找到存储桶,该元素就会添加到存储桶的末尾。
当Gridsort检测到已排序的数据时,它将切换到自适应二进制搜索。
四排序
某个存储桶溢出后,将使用排序对其进行并创建一个新的存储桶。 排序后的数据在两个存储桶之间分配,因此每个存储桶都充满了一半。 每个存储桶中最低的元素将添加到查找表中。
结束
将所有元素都插入二进制多维数据集后,每个存储桶