归并排序

归并排序采用分治策略

  • 分：从q分开成$A[1…q]$和$A[q+1…n]$两个子序列
  • 治：子序列递归执行归并排序
  • 合：将子序列执行的结果组合在一起

归并排序与快排不同的在于关键步骤不同

快排是“分”下了功夫，而归并是“合”做了处理

在“治”之后，两个子序列都是有序的，我们设想有一个output pile而两个子序列是一个从小到大的pile，

我们从上面开始一一比较，将较小者假如output pile，然后有一组先取完，另一组的是除output pile中外最大的元素且有序，因此直接放入即可

这就给了归并排序“合”的灵感

递归伪码

1
2
3
4
5
6
MERGESORT(A,p,r)
if p < q
	q ← floor[(r-p)/2]
	MERGESORT(A,p,q)
	MERGESORT(A,q+1,r)
	MERGE(A,p,q,r)

根据上面所说栗子得到的启示：$A[p…q]$的元素注入$L[1…n_1+1]$，其中$n_1=Length(A[p…q])$，$A[q+1…r]$的元素注入$R[1…n_2+1]$，其中$n_2=Length(A[q+1…r])$,这两个序列都是已排序的，这里我们多设置了一位表示Bottom，如果是<谓词，那么应该设置为至少比另一个序列的所有元素都大，反之，应该比另一个序列的所有元素都小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
MERGE(A,p,q,r)
n1 ← q-p+1
n2 ← r-q

let L[1...n1+1] and R[1...n2+1]

L[n1+1] ← ∞
R[n2+1] ← ∞

L[1...n1] ← A[p...q]
R[1...n2] ← A[q+1...r]

i ← 1
j ← 1
for k ← p to r do
 if L[i] <= R[j]
  then A[k] ← L[i]
       i ← i+1
  else A[k] ← R[j]
  	   j ← j+1

时间复杂度显然为$O(n)$

算法正确性

我们用循环不变式来证明算法是正确的

L15-20:在每次for循环迭代之前，$A[p…k-1]$包含$k-p$个最小元素，且$L[i]$和$R[j]$分别是$L$和$R$中未进入$A$的最小元素

  • 初始：在第一次for循环开始前，显然，$A$还未开始加入任何最小元素，且$L[1]$和$R[1]$都未进入$A$且为最小元素
  • 维持：假设上一次for循环迭代时满足循环不变式，此时，根据上面的逻辑，我们会将此时$L[i…n_1+1]$或是$R[j…n_2+1]$中的最小元素加入$A$（实际上此时$A[p…k]$包含$k-p+1$个最小元素，但是$k$会自增）且对应的最小元素的下标会进一，因此循环不变式得以保持
  • 终止：当循环终止时，$A[p…r]$包含$r+1-p$个最小元素，即已排序完成