MergeSort实现异常求助：递归逻辑导致排序结果不正确问题排查

我正尝试基于《算法导论》中的伪代码在Python中实现归并排序，但当前版本可编译运行，但列表未正确排序。

我的代码如下：

import math
def MergeSort(A,p,r):
    if(p>=r):
        return
    q=math.floor((p+r)/2)
    MergeSort(A,p,q)
    MergeSort(A,q+1,r)
    Merge(A,p,q,r)
def Merge(A,p,q,r):
    nL=q-p
    nR=r-q
    L=[0]*nL
    R=[0]*nR
    for i in range(0,nL):
        L[i]=A[p+i]
    for j in range(0,nR):
        R[j]=A[q+j]
    i=0
    j=0
    k=p
    while i < nL and j < nR:
        if L[i] <= R[j]:
            A[k]=L[i]
            i=i+1
        else:
            A[k]=R[j]
            j=j+1
        k=k+1
    while i<nL:
        A[k]=L[i]
        i=i+1
        k=k+1
    while j < nR:
        A[k]=R[j]
        j=j+1
        k=k+1

A=[20,52,35,22,90,12,5]
MergeSort(A,0,len(A))
print(A)

错误集中在递归逻辑部分：

if(p>=r):
    return
q=math.floor((p+r)/2)
MergeSort(A,p,q)
MergeSort(A,q+1,r)

如果去掉q+1会导致递归无法终止，保留则排序结果错误。我已有可正常运行的修正版本，但希望让当前更贴近《算法导论》伪代码的版本正常工作，同时理解错误原因（刚接触递归）。

错误原因分析 #

问题核心在于索引范围的定义和《算法导论》伪代码的差异：

• 《算法导论》中归并排序的伪代码通常定义r为子数组的最后一个元素的索引（闭区间[p, r]），但你调用MergeSort(A,0,len(A))时，r传入的是列表长度，这是开区间的右边界（实际有效索引是0到len(A)-1）。
• 递归分割时，q=math.floor((p+r)/2)在r是开区间边界时，分割逻辑和闭区间的伪代码不匹配：
  比如当p=0, r=7（对应列表7个元素，索引0-6），q=3，此时左子数组应该是[0,2]（对应前3个元素），右子数组是[3,6]（后4个元素），但你的代码里MergeSort(A,p,q)是[0,3]，包含了索引3的元素，MergeSort(A,q+1,r)是[4,7]，而索引7不存在，导致Merge函数处理了空的右子数组，最终排序错误。

修正方案（贴近伪代码） #

要完全贴合《算法导论》的闭区间逻辑，需要做两处修改：

1. 调用时传入r为最后一个元素的索引，即MergeSort(A,0,len(A)-1)
2. 调整Merge函数中左右子数组的长度和赋值逻辑：
   • nL = q - p + 1（因为闭区间[p, q]的元素个数是q-p+1）
   • nR = r - q（闭区间[q+1, r]的元素个数是r-(q+1)+1 = r-q）
   • 赋值右子数组时，R[j] = A[q+1+j]（因为右子数组从q+1开始）

修正后的完整代码：

import math
def MergeSort(A,p,r):
    if(p>=r):
        return
    q=math.floor((p+r)/2)
    MergeSort(A,p,q)
    MergeSort(A,q+1,r)
    Merge(A,p,q,r)
def Merge(A,p,q,r):
    nL=q-p+1  # 修正：闭区间[p,q]的元素个数
    nR=r-q    # 修正：闭区间[q+1,r]的元素个数
    L=[0]*nL
    R=[0]*nR
    for i in range(0,nL):
        L[i]=A[p+i]
    for j in range(0,nR):
        R[j]=A[q+1+j]  # 修正：右子数组起始索引是q+1
    i=0
    j=0
    k=p
    while i < nL and j < nR:
        if L[i] <= R[j]:
            A[k]=L[i]
            i=i+1
        else:
            A[k]=R[j]
            j=j+1
        k=k+1
    while i<nL:
        A[k]=L[i]
        i=i+1
        k=k+1
    while j < nR:
        A[k]=R[j]
        j=j+1
        k=k+1

A=[20,52,35,22,90,12,5]
MergeSort(A,0,len(A)-1)  # 修正：r传入最后一个元素的索引
print(A)

为什么原代码会出错？ #

原代码中r是开区间边界，导致：

• 递归分割时，左子数组包含了本该属于右子数组的元素，右子数组可能超出有效索引范围
• Merge函数中右子数组的赋值R[j]=A[q+j]，当q是中间位置时，会重复取到左子数组的最后一个元素，最终合并时数据混乱，排序结果错误

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