“ 5美分”谈排序

在继续本主题时，我想分享我的代码，该代码从GNU C ++库的当前版本替代std::sort() ，并且（大约没有确切的数据）在CppCon 2019上重复“ Sort Alexandrescu”的结果。

任务条件

在代码（不是C++ ）中，为了摆脱使用qsort()库的开销，花了合理的努力使排序不比std::sort()差。 因此，包括使用宏而不是模板。
反过来，如果您对“小鼠”而不是“大象”进行排序，则qsort()的开销将非常大：额外的地址算法和对比较器函数的间接调用。

结果

根据可获得的信息，在实践意义上， 这种算法和实现功能的组合比许多其他选项要快：

• 通过比较和移动的数量（通过用C++类代替比较和分配计数来测量）。
• 取决于机器代码的数量（在缓存中仅占很小的空间）。
• 通过源代码的数量及其透明度。
• 在长随机序列上，取决于SORT_THRESHOLD ，增益趋向于3-5％。
• 使用有序或主要有序数据的速度提高了1.5-2-3倍。
• 仅在非常短的序列中以相反的顺序会产生轻微的损失。

这个选项很可能比绝大多数种类的选项稍快和/或稍慢，但是发现这实际上是我无法承受的泰坦尼克号工作。

有趣的是，有人将此选项与Tarantool，PostgreSQL，SQLite和MySQL中的当前选项进行了比较。 我希望kaamos不能通过其SysBench通过 。

亚历山德列斯库怎么样？

在RPG18的第一条评论中，有一个链接与Andrei Alexandrescu的最新表演“在人们的思想中发现速度”有关 ，他提出了一个非常相似的想法，但在进入最终决赛之前进入了heap_sort。

对我来说，表演似乎有点延长了（如果olegbunin至少给了90分钟一次……），但是这个数字还不够。 特别是，我希望看到N增大时的排序行为，因为QuickSort完成阈值的增大会导致大尺寸时加速，而小尺寸时减速，等等。

然而，根据亚历山大·库斯库（Alexandrescu）引用的数据判断，所描述的选项突然提供了类似的加速。 但是，直到我找到以最终形式显示给Alexandrescu的代码为止，才能“进行比较”，而且没有时间按视频进行编码（如果找到或编写，则编写）。

思想方面

“算法”的理论和思想方面非常简单：

1. 对于非短序列，我们将QuickSort与所有可接受的优化配合使用：
   
   • 不递归使用指针的内部位置堆栈。
   • 作为支持元素，我们使用第一个，中间和最后一个元素的中位数。
   • 我们不会对一小部分进行排序，而是将其留给ShellSort。
   • 拆分后，我们总是将最大的部分放在堆栈上；结果，堆栈不能比Log2(N)更深。
2. 使用ShellSort添加排序数据：
   
   • 最小通过次数。
   • 第一遍的步骤与未排序的片段的最大大小相关。
   • 步骤8和（不可避免）1.总共只有两次通过。
3. 使用ShellSort可以相对安全地提高QuckSort的退出阈值。 因此，我们结合了最好的QuickSort选项之一，并且由于退出时间较早且预分类速度稍快而节省了费用。

值得注意的是，根据处理器的体系结构和应用条件，可以通过在128-256之内选择SORT_THRESHOLD将长序列的增益提高10-15％。 但是，这减慢了具有相反顺序并接近顺序的序列的处理。
但是，如果您了解数据中不太可能出现逆序，或者您可以廉价地检测到这种情况并使用较小的SORT_THRESHOLD执行分支，则这是一个不错的SORT_THRESHOLD 。

聚苯乙烯
对于我的libmdbx项目（带有ACID的快速嵌入式键值数据库），所描述的排序选项是“重做”， 前几天README和API描述已更新（实际上已重写）。 因此，我将感谢您纠正错别字和建议。 通常，自己并不缺少一些信息。