在python中实现合并排序

我正在尝试在Python 3中实现合并排序算法。以下是实现算法合并部分的函数：

def Merge(A,p,q,r):
n1 = q - p + 1
n2 = r - q

#We first populate two lists that contain the sorted subsequences A[p,...,q] and A[q+1,...,r]
L = []
R = []

for index in range(n1):
    L.append(A[index + p])

for index in range(n2):
    R.append(A[index + q + 1])

#We now overwrite the A[p,..,q,...r] section of the list by comparing the 'top-most'
#elements in the lists l and R and putting the smaller element in the corresponding
#entry in A. If one of the list is fully exposed/no longer available, we simply put the 
#remaining list's elements in the corresponding positions in A.

i = 0
j = 0

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

    if i > n1-1:
        A[k] = R[j]
        j = j + 1

    elif j > n2-1:
        A[k] = L[i]
        i = i + 1

    elif L[i] < R[j]:
        A[k] = L[i]
        i = i + 1

    else:
        A[k] = R[j]
        j = j + 1 

return A   

我已经测试了此函数，并且运行良好：只要对子数组A [p，q]和A [q + 1，r]进行了排序，整个数组A [p，r]就会正确地进行排序。我现在尝试实现分而治之的方法来合并足够大的列表。

import math

def Merge_Sort(A,p,r):

if p == r:

    return A

if p < r:

    q = math.floor((p+r)/2)
    Merge_Sort(A,p,q)
    Merge_Sort(A,q+1,r)
    Merged_List = Merge(A,p,q,r)

return Merged_List

但是我运行它时会得到错误的答案。这是一个例子：

#We now analyze the merge sort algorithm.
A = [1,7,9,3]
B = Merge_Sort(A,0,3)
print(B)

输出是

[3, 9, 3, 9]

我可能在分而治之的实现过程中犯了一些明显的/愚蠢的错误。有什么建议吗？