CLRS归并排序实现遇索引越界及排序失败问题排查求助

为什么这段代码无法对随机数组排序？
我试着调整了索引但没用，也考虑了Python的零基索引做了调整，但还是得不到有序数组。我是按照《算法导论》（第三版）31页的算法实现的。

import numpy as np
import math

X = np.random.randint(0,10,10).tolist()

def merge(a, p, q, r):
    n1 = q - p + 1
    n2 = r - q

    L = [0] * (n1 + 1)
    R = [0] * (n2 + 1)

    for i in range(0, n1):
        L[i] = a[p + i - 1]

    for j in range(0, n2):
        R[j] = a[q + j]

    L.append(math.inf)
    R.append(math.inf)

    i = 0
    j = 0

    for k in range(p, r):
        print(k)
        if L[i] <= R[j]:
            a[k] = L[i]
            i += 1
        else:
            a[k] = R[j]
            j += 1

def mergesort(a, p, r):
    if p < r:
        q = (p + r)//2
        mergesort(a, p, q)
        mergesort(a, q+1, r)
        merge(a, p, q, r)

print("Before: {}\n".format(X))
mergesort(X,0,10)
print("After: {}".format(X))

我帮你排查了几个核心问题，全都是因为把CLRS里的1基索引直接套用到Python的零基索引上导致的，逐个拆解：

1. 左子数组L的填充索引错误 #

CLRS伪代码用的是1基索引，所以原代码里L[i] = a[p + i - 1]是1基的写法，但Python是零基，当p=0时，p+i-1会变成-1，直接取数组最后一个元素，完全偏离了要取的左子数组范围。修正为：

for i in range(0, n1):
    L[i] = a[p + i]

这样零基下的a[p], a[p+1], ..., a[q]会被正确填充到L数组中。

2. 右子数组R的填充索引错误 #

同样是1基转零基的问题，右子数组应该从q+1开始到r，原代码R[j] = a[q + j]会把左子数组的最后一个元素a[q]也包含进来，导致数据重复和遗漏。修正为：

for j in range(0, n2):
    R[j] = a[q + 1 + j]

3. 哨兵元素的添加方式错误 #

你先初始化L为[0]*(n1+1)（长度为n1+1），然后又用L.append(math.inf)，这样L的长度会变成n1+2，哨兵位置完全错位。CLRS里是把哨兵放在子数组的最后一个位置，直接覆盖初始化的最后一个0即可，不用append：

# 替换原来的append语句
L[n1] = math.inf
R[n2] = math.inf

4. 归并循环的范围错误 #

原代码for k in range(p, r)是左闭右开的范围，会漏掉r位置的元素。我们需要覆盖从p到r的所有索引（包含r），所以改成：

for k in range(p, r + 1):

5. 归并排序的调用参数错误 #

你的数组X长度是10，索引范围是0-9，但调用mergesort(X,0,10)时，r=10已经超出了数组的最大索引（9），会导致后续递归中访问a[10]触发索引越界。修正为：

mergesort(X, 0, len(X)-1)

修正后的完整代码：

import numpy as np
import math

X = np.random.randint(0,10,10).tolist()

def merge(a, p, q, r):
    n1 = q - p + 1
    n2 = r - q

    L = [0] * (n1 + 1)
    R = [0] * (n2 + 1)

    for i in range(0, n1):
        L[i] = a[p + i]

    for j in range(0, n2):
        R[j] = a[q + 1 + j]

    L[n1] = math.inf
    R[n2] = math.inf

    i = 0
    j = 0

    for k in range(p, r + 1):
        if L[i] <= R[j]:
            a[k] = L[i]
            i += 1
        else:
            a[k] = R[j]
            j += 1

def mergesort(a, p, r):
    if p < r:
        q = (p + r)//2
        mergesort(a, p, q)
        mergesort(a, q+1, r)
        merge(a, p, q, r)

print("Before: {}\n".format(X))
mergesort(X, 0, len(X)-1)
print("After: {}".format(X))

运行这个版本就能得到正确的排序结果了~

备注：内容来源于stack exchange，提问作者Brady