证明归并排序的正确性

February 01, 2019

证明归并排序的正确性。

首先证明两个有序子序列 A[1..m]A[1..m]A[m+1..n]A[m+1..n] 的归并结果 B[1..n]B[1..n] 也是有序的。

命题 P(k)P(k):最后 kk 次归并出的 B[nk+1..n]B[n-k+1..n] 子序列有序。

P(1)P(1) 明显成立。

假如 P(k)P(k) 成立。分析算法可以推出,倒数第 k+1k+1 次操作选取的(即B[nk]B[n-k])是剩下最小,又 B[nk+1..n]B[n-k+1..n] 有序,所以 B[nk..n]B[n-k..n] 有序性。即 P(k+1)P(k+1) 也成立。

由归纳原理知 P(n)P(n) 成立:即最后 nn 次归并结果 B[1..n]B[1..n] 有序。

命题 Q(n)Q(n): 对 A[1..n]A[1..n] 归并排序,得到有序序列。

需要使用到强归纳原理

强归纳原理

对于任意 m0Nm_{0}\in \mathbb{N} 、关于自然数的命题 QQ,如果 m0m<nm_{0} \leq m \lt nQ(m)Q(m) 为真能得到 Q(n)Q(n) 为真,那么对所有 m0nm_{0} \leq n 都有 Q(n)Q(n) 为真。

这里命题 Q(n)Q(n) 的正确性决定于两个“子问题”的命题 Q(m)Q(m)Q(nm)Q(n-m) 的正确性以及已经得证的 P(n)P(n)

m0m_{0} 设为 00

n>1n \gt 1 时,可以取 mmnmn-m 都小于 nn,符合强归纳的假设。

n=1n = 1 时,Q(1)Q(1) 即使分下去也只能分成 Q(1)Q(1)Q(0)Q(0),这是递归基,我们需要特殊考虑:0m<10 \leq m \lt 1时,Q(0)Q(0) 成立,Q(1)Q(1) 也显然成立,也满足强归纳的假设部分。

所以 Q(n)Q(n) 对所有自然数 nn 都成立。