sorting - 比较排序算法在每一步评估超过 2 个元素

Question

比较排序算法通常在每一步评估 2x 个元素（如果第一个元素小于/大于或等于第二个元素，则执行不同的操作。）

有哪些排序算法的例子，最好是稳定的，每一步可以比较超过 2 个元素？

他们的表现将如何评估？

对于一次排序 2 个元素，比较排序的性能不能比O(n log n)平均水平更好，一次排序 3、4、5+ 个元素的性能限制是多少？

Answer 1

k-way归并排序需要确定k个元素中的哪个是最小的。使用标准的 2x 比较，需要 3 次比较才能确定最小的元素。对于基于内存的排序，4 路归并排序将采用与 2 路归并排序大致相同的操作数量，但由于缓存更友好，运行时间略有改善。在这个答案的末尾有一个 4 路合并排序的例子：

优化的归并排序比快速排序更快

在一个有 16 个寄存器的系统上，4-way 大约是你能达到的最高值。另外，尝试在不使用堆的情况下实现这一点（这会导致算法变慢）需要一个大的 if | 嵌套树。其他语句。在上面链接的那个答案中，它在 4 路合并排序中已经足够复杂了。

Answer 2

一次任何 n 元素（对于指定的固定 n）比较可以通过一系列固定数量的 2 元素一次比较来模拟。如果您可以比O(n log n)一次 n 次做得更好，它会自动为您提供比一次O(n log n)2 次更好的算法。