可能的重复：
为什么合并排序中的合并操作是O(n)？
为什么每次迭代都恰好需要 O(n) 关于合并排序 有人可以详细解释一下吗？ 为什么C_merge(n)= O(n)？这是否意味着合并两个排序数组的时间。
这个想法是，我们有两个排序数组，而不是两个数组，其中一个数组的最小元素大于另一个最高的元素。我想说的是，这不是[1, 3, 9, 12]和[13, 17, 19].但它更像是[3, 12, 13, 17]和[1, 9, 19].
你看，在以后的情况下，你不能附加它们。那么，你如何结合呢？您遵循以下算法：
- 假设第一个有
m元素，第二个有n。你制作一个大小为m+n的辅助数组。这将存储最终的组合和排序数组。 - 分配两个光标 -
i和j，指向数组的头部。 - 比较
i和j处的元素;选择较小的元素。复制值辅助数组，并将光标移动到较小的光标上。 - 重复 #3，直到其中一个数组耗尽;然后将其余元素从未耗尽的数组复制到辅助数组。
因此，在我们的例子中，您比较(3, [1]); ([3], 9); (12, [9]); ([12], 19); ([13], 19); ([17], 19); (--, [19]).你看？如何比较？(m+n).假设每个操作O(1).长度(m+n)数组的合并过程O(m+n)。
在最好的情况下，您将有排序的数组作为输入。在这种情况下，要合并的两个子数组只需要连接。但是我们将应用上面提到的通用算法。在这种情况下，您将必须比较和复制min(m,n)元素;然后将max(m,n)元素复制到辅助数组。无论如何，您将拥有全面的(m+n)操作。