2-way Merge Sort 和归并排序

Question

2 向合并排序与递归合并排序有何不同？

---

假设有5个数8,9,1,6,4需要排序 在合并排序中，我们这样划分 第一步：{8,9,1} {6,4}

第 2 步：{8,9} {1} {6} {4}

第 3 步：{8} {9} {1} {6} {4}

现在合并

第四步：{8,9} {1} {4,6}

第 5 步：{1,8,9} {4,6}

第六步：{1,4,6,8,9}

但是在2路合并排序中，我们将数组分成2个元素（但是根据维基百科，在合并之前每2个元素部分需要排序。https://en.wikipedia.org/wiki/K-way_merge_algorithm）所以，它也是从单个开始元素并合并它们 正确的？ 所以，数组的步骤：8,9,1,6,4

Step1:{8,9} {1,6} {4}【最后就是奇数元素合并】

第二步：{1,6,8,9}。 {4}

第 3 步：{1,4,6,8,9}

所以，这里的步骤数减少了。那么它的算法是什么？ 2-way merge sort归并排序是否比归并排序更高效？

Answer 1

Is 2-way merge sort merge sort more efficient than merge sort?

迭代 2 向合并排序的另一个名称是自下而上的合并排序，而递归合并排序的另一个名称是自上而下的合并排序。

一般来说，优化的自下而上合并排序比优化的自上而下合并排序稍微更有效。自上而下归并排序对数组递归"splitting"生成的索引进行O(n)次栈操作。如果 n 不是 2 的幂，那么自下而上归并排序会进行更多的比较和移动，但它比自上而下归并排序的堆栈操作开销要小。对于大型阵列，差异小于 5%。

对于混合插入/合并排序，在 n / m 组 m[ 上使用插入排序=23=]元素，自底向上归并排序可以调整m来处理n不是2的幂

自上而下的合并排序主要用于学习。尽管在性能和堆栈上存在微小差异 space，但大多数库都使用自底向上合并排序的一些变体来实现稳定排序。