MergeSort 实现无法正常工作

Question

我一直在《算法简介》一书中尝试用Python实现MergeSort，但我不知道为什么这个版本不能正常工作（它确实可以编译，但列表没有正确排序）。 我的代码：

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 时，递归永远不会结束，但当它不是 q+1 时，它不会给出正确的输出 有效的代码：

import math

def MergeSort(A, p, r):
    if p < r - 1:
        q = (p + r) // 2
        MergeSort(A, p, q)
        MergeSort(A, q, 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(nL):
        L[i] = A[p + i]
    for j in range(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 += 1
        else:
            A[k] = R[j]
            j += 1
        k += 1
    while i < nL:
        A[k] = L[i]
        i += 1
        k += 1
    while j < nR:
        A[k] = R[j]
        j += 1
        k += 1

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

我想让我的版本正常工作，因为它与书中的伪代码最相似，并且还了解为什么这个版本不正确，因为我才开始使用递归。

Answer 1

这是正确的版本：

import math


def MergeSort(A, p, r):
    if p < r:
        q = p + (r - p) // 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
    nR = r - q
    L = [0] * nL
    R = [0] * nR
    for i in range(nL):
        L[i] = A[p + i]
    for j in range(nR):
        R[j] = A[q + j + 1]
    i = 0
    j = 0
    k = p
    while i < nL and j < nR:
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
        k += 1
    while i < nL:
        A[k] = L[i]
        i += 1
        k += 1
    while j < nR:
        A[k] = R[j]
        j += 1
        k += 1


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