mergesort - 为什么归并排序中的归并操作是 O(n)？

Question

对于合并排序分治操作，自底向上合并阶段需要多少时间？我的导师说它是线性的，因此它将是O(n)。但我没明白。它将如何是线性的？

合并操作如何是线性的O(n)？

Answer 1

两个数组的合并操作，是扫描数组并选择两个数组中的最低值/最高值。

所以你有了

a: [1, 3, 6, 7]
b: [4, 5, 7, 8]

你像这样比较（某种伪代码）

indexA = 0;
indexB = 0;
auxilaryArray = [];
indexAux = 0;

while true 
   if indexA > len(a)-1 or indexb > len(b) -1  
       break
   # you are cherry picking one from the two array which is lesser
   # until any one of these array exausts
   if(a[indexA] > b[indexB])
       auxilaryArray[indexAux++] = b[indexB++]
   else
       auxilaryArray[indexAux++] = a[indexA++]

#append the remaining array 
while indexA < len(a)
    auxilaryArray[indexAux++] = a[indexA++]

#appends the remaining array
while indexB < len(b)
    auxilaryArray[indexAux++] = b[indexB++]

你看如果数组a[k]，三个循环的迭代总和b[m]将是。k+m

---

如果

a: [1, 3, 6, 7]
b: [4, 5, 7, 8]

这是第一个循环：

(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (3, 2) # 6 iterations; array a exhausted

第二个循环不会运行，因为a已经扫描。

第三个循环追加

b[2], b[3]   # 2 iterations; b exhaused

你看到8 = 4 + 4循环运行了吗？什么顺序O(n)。

---

在 Mergesort 中，除法运算是对数ln n的，合并部分是线性的。由于您划分并合并回来，因此顺序变为乘法，因此 Mergesort 是O(nln(n)).

与冒泡、选择、插入排序不同，您从左到右扫描 (O(n))，然后通过连续交换（冒泡）或通过扫描未排序数组的其余部分中的最小值（选择）或通过在数组的已排序部分的正确位置插入（插入）——这些操作是 O(n)...所以这些算法的总顺序变为 O(n ² )