python - 从伪代码python实现合并排序的问题

Question

我正在尝试基于以下伪代码在 Python 中实现归并排序。我知道那里有很多实现，但我一直无法找到一个遵循这种模式的实现，它在末尾有一个 for 循环而不是 while 循环。此外，将子数组中的最后一个值设置为无穷大是我在其他实现中从未见过的。注意:以下伪代码具有基于 1 的索引，即索引从 1 开始。所以我认为我最大的问题是正确设置索引。现在它只是没有正确排序并且很难用调试器跟踪。我的实现在底部。

当前输出:

Input:  [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
Merge Sort:  [0, 0, 0, 3, 0, 5, 5, 5, 8, 0]

def merge_sort(arr, p, r):
    if p < r:
        q = (p + (r - 1)) // 2
        merge_sort(arr, p, q)
        merge_sort(arr, q + 1, r)
        merge(arr, p, q, r)

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] = 10000000 #dont know how to do infinity for integers
    R[n2] = 10000000 #dont know how to do infinity for integers

    i = 0
    j = 0

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

    return A

Answer 1

首先，您需要确定由 p 和 r 表示的区间在其端点处是开还是闭。伪代码(for 循环包括最后一个索引)确定区间在两个端点都是闭合的:[p, r]。

考虑到最后的观察，您可以注意到 for k in range(p, r): 不检查最后一个数字，因此正确的行是 for k in range(p, r + 1):.

您可以通过使用 [p, r] 加一范围内的 A 的最大元素来表示问题中的“无穷大”。这将使工作完成。

您不需要返回数组 A，因为所有更改都是通过它的引用完成的。

此外，q = (p + (r - 1))//2 没有错(因为 p < r)，但正确的等式是 q = (p + r)//2 作为您想要的两个数字的中间整数值的间隔。