mergesort - 我正在尝试在 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]。

如果有一个数字比它前面的数字大，输出就会出错

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)

标签： mergesort

Answer 1

这里有一个问题：

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

通常，合并排序将高设置为结束索引 = 1 + 最后一个索引。这意味着排序将需要检查 (high - low) > 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)