《算法导论》（第4版）归并排序2.3-2问题逻辑困惑

问题背景 #

原问题描述：

归并排序（Merge-Sort）过程第1行的判断条件是“if p >= r”而非“if p != r”。若调用Merge-Sort时p > r，则子数组A[p : r]为空。请证明：只要初始调用Merge-Sort(A, 1, n)满足n >= 1，使用“if p != r”作为判断条件就能确保不会出现p > r的递归调用。

归并排序原伪代码：

Merge-Sort(A, p, r)
1    if p >= r
2        return
3    q = math.floor((p + r) / 2)
4    Merge-Sort(A, p, q)
5    Merge-Sort(A, q + 1, r)
6    // Merge A[p : q] and A[q + 1 : r] into A[p : r]
7    Merge(A, p, q, r)

你的疑问是：若将第1行条件改为if p != r，当n=1时调用Merge-Sort(A, 1, 1)，条件判断为假，跳过return，计算q=1后执行第5行调用Merge-Sort(A,2,1)，出现了p>r的情况。

你的推理错误点 #

核心错误是完全搞反了“使用‘if p != r’作为判断条件”的逻辑：
原问题中的“使用‘if p != r’作为判断条件”，指的是仅当p≠r时才执行递归拆分逻辑，否则直接终止递归——也就是正确的代码结构应该是：

Merge-Sort(A, p, r)
1    if p == r  // 等价于“当p != r时才执行后续代码”
2        return
3    q = math.floor((p + r) / 2)
4    Merge-Sort(A, p, q)
5    Merge-Sort(A, q + 1, r)
6    Merge(A, p, q, r)

而非你理解的把原条件改成if p != r就return（这会导致p≠r时终止，完全违背问题意图）。

正确的证明思路 #

我们用数学归纳法证明：对于任意初始调用Merge-Sort(A,1,n)（n≥1），所有递归调用的参数都满足p ≤ r：

• 基础情况：n=1时，调用Merge-Sort(A,1,1)，因p==r直接return，无后续递归调用，自然不会出现p>r的情况。
• 归纳假设：假设对于所有长度k < n的子数组，调用Merge-Sort(A,p,r)（其中r-p+1=k）时，所有递归调用的参数都满足p≤r。
• 归纳步骤：对于长度为n的子数组，调用Merge-Sort(A,p,r)（r-p+1=n≥2，故p≠r）：
  1. 计算q = floor((p+r)/2)，此时p ≤ q < r（因为p<r，整数除法向下取整）。
  2. 第一个递归调用Merge-Sort(A,p,q)：子数组长度为q-p+1 ≤ n/2 < n，根据归纳假设，不会出现p>r的调用。
  3. 第二个递归调用Merge-Sort(A,q+1,r)：因q < r，故q+1 ≤ r，子数组长度为r-(q+1)+1 = r-q ≤ n/2 < n，同样根据归纳假设，不会出现p>r的调用。

综上，所有递归调用的参数都满足p≤r，不会出现p>r的情况。

内容的提问来源于stack exchange，提问作者Yann Rand