我尝试用python编写一个合并排序，但是当我输入不同的列表时，输出是不同的

Question

当我的输入是[6,5,4,3,2,1]时，输出是[1,2,3,4,5,6]，

但是当我的输入是[1,2,3,4,5,6]时，输出将变为[1,1,1,1,1,1,1]。

如果有一个数字大于它前面的数字，输出将变得错误

def merge (arr,low,mid,high):    
L=arr[low:mid+1]
R=arr[mid+1:high+1]
i=0
j=0
k=low
while i<len(L) and j<len(R):
if L[i]<=R[j]:
arr[k]=L[i]
i+=1
k+=1
else:
arr[k]=R[j]
j+=1
k+=1
while i<len(L):
arr[k]=L[i]
i+=1
k+=1
while j<len(R):
arr[k]=L[j]
j+=1
k+=1
def sort (arr,low,high):
if low<high:
mid=low+(high-low)//2
print(mid)
sort(arr,low,mid)
sort(arr,mid+1,high)
merge(arr,low,mid,high)
arr=[1,2,3,4,5]
print(arr)
sort(arr,0,len(arr)-1)
print(arr)

Answer 1

这里有一个问题：

while j<len(R):
arr[k]=R[j]    # this was arr[k]=L[j]

通常，合并排序将高设置为结束索引 = 1 + 最后一个索引。这意味着排序需要检查(高 - 低(> 1，但它消除了 +1。

def merge (arr,low,mid,high):    
L=arr[low:mid]
R=arr[mid:high]
i=0
j=0
k=low
while i<len(L) and j<len(R):
if L[i]<=R[j]:
arr[k]=L[i]
i+=1
k+=1
else:
arr[k]=R[j]
j+=1
k+=1
while i<len(L):
arr[k]=L[i]
i+=1
k+=1
while j<len(R):
arr[k]=R[j]
j+=1
k+=1
def sort (arr,low,high):
if (high - low) > 1:          # if < 2 elements, nothing to do
mid=low+(high-low)//2
sort(arr,low,mid)
sort(arr,mid,high)
merge(arr,low,mid,high)
arr=[3,2,1,5,4]
print(arr)
sort(arr,0,len(arr))              # len(arr) = ending index of arr
print(arr)