CLRS第4版mergeSort终止条件（问题2.3-2）

Question

问题（根据ERATA修正）： mergeSort 过程的第 1 行中的测试读取为

if p >= r

而不是

if p == r.

如果使用 p > r 调用 mergeSort，则子数组 A[p:r] 为空。 论证只要

mergeSort(A, 1, n)

的初始调用具有

n >= 1

，测试

if p == r

就足以确保没有递归调用具有

p > r

。

def mergeSort(arr, p, r):
    if p >= r:                  #line 1
        return                  #line 2
    q = math.floor((p+r)/2)     #line 3
    mergeSort(arr, p, q)        #line 4
    mergeSort(arr, q+1, r)      #line 5
                                #line 6
    merge(arr, p, q, r)         #line 7

我尝试的解决方案： 对于第 4 行，基于初始条件和 q 是 p 和 r 之间的中点这一事实，p 始终小于或等于 r。 我遇到了第 5 行的问题，如果我有一个包含单个元素的数组，那么第 4 行很好，但对于第 5 行，q+1 导致 p > r 我错过了什么？

Answer 1

如果我有一个包含单个元素的数组，那么...

然后

p == r

，您在第 2 行返回，但没有到达第 5 行。