algorithm - 插入排序与合并排序：哪个更快取决于数组？

Question

假设给定一个数组 A 已经按升序排序。插入排序或合并排序哪个渐近更快？

同样，假设我们有一个按降序排序的数组 B，所以它需要反转。现在哪个渐近更快？

我很难理解这一点，我已经知道插入排序更适合较小的数据集，而合并排序更适合较大的数据集。但是，我不确定为什么一个比另一个快，这取决于数据集是否已经排序。

标签： algorithmsortingcomplexity-theorymergesortinsertion-sort

Answer 1

说到最坏的情况，合并排序与O(N logN)插入O(N^2)排序相比更快。然而，算法的另一个特征是欧米茄 - 最佳情况复杂度，这是Omega(N)针对Omega(N logN)合并排序的插入排序。
后者可以在查看手头的算法时进行解释：

1. 合并排序的工作原理是将数组分成两半（如果可能），递归地对这些两半进行排序并合并它们。看看它如何不依赖于元素的实际顺序：我们将进行递归调用，无论我们正在排序的部分是否已经按顺序排列（除非它是基本情况）。
2. 插入排序寻找第一个不符合预期顺序的元素，并将其向左移动，直到它按顺序排列。如果没有这样的索引，则不会发生移位，算法将完成，只O(N)进行比较。

但是，合并排序在最佳运行时间方面是完全可以修复的！您可以在进入递归之前检查手头的部分是否已经排序。这不会改变 的最坏情况复杂度O(N logN)（但是，常数会加倍），但会将最佳情况复杂度带到Omega(N).
在数据以相反顺序排序的情况下，插入排序的最坏情况会出现，因为我们必须将每个元素（按迭代顺序）从其位置移动到第一个位置，进行N(N-1)/2交换，这属于O(N^2). 然而，O(N logN)由于它的递归方法，归并排序仍然需要。