# python中的合并排序

abpan8
``````def get_random_array(n):
return [random.randint(0, 10000) for _ in range(n)]

def test_sorting_algorithm(algorithm):
for _ in range(100):
A = get_random_array(random.randint(0, 1000))
A_sorted = algorithm(A)
assert A_sorted == sorted(A), "FAIL!"

def merge(A,l,m,r):

i = l
j = m+1
new = []

while i <= m and j <= r:
if A[i] <= A[j]:
new.append(A[i])
i += 1
else:
new.append(A[j])
j += 1

while i <= m:
new.append(A[i])
i += 1

while j <= r:
new.append(A[j])
j += 1

return new

def mergeSort_rec(A, l, r):

if l < r:
m = (l+(r-1))//2  # Same as (l+r)//2, but avoids overflow for large l and h
# Sort first and second halves
mergeSort_rec(A, l, m)
mergeSort_rec(A, m+1, r)
merge(A, l, m, r)

def mergeSort(B):
A = B[:] # Copy the array just because we decided to return a sorted copy of the original array
mergeSort_rec(A, 0, len(A)-1)
return A

A = get_random_array(10)

test_sorting_algorithm(mergeSort)
``````

`test_sorting_algorithm`返回FAIL。此代码不起作用，因为`merge`函数中有错误，您能帮我了解错误是什么以及如何修复它吗？此外，我不明白这条评论“#Same as (l+r)//2，但避免大 l 和 h 溢出”的意义，你能解释一下这是什么意思吗？

``````return new
``````

0 条评论