algorithm - 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 个元素(但根据 wikipedia ，在合并之前每 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}

第三步:{1,4,6,8,9}

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

Answer 1

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

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

通常，优化的自下而上归并排序比优化的自上而下归并排序稍微高效一些。自顶向下合并排序对数组的递归“拆分”生成的索引执行 O(n) 堆栈操作。如果 n 不是 2 的幂，那么自下而上归并排序会进行更多的比较和移动，但它比自上而下归并排序的堆栈操作开销要小。对于大型阵列，差异小于 5%。

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

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