有人可以帮我弄清楚我的合并排序实现有什么问题吗？

Question

我的实现：

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    left = arr[:len(arr)//2]
    right = arr[len(arr)//2:]

    merge_sort(left)
    merge_sort(right)

    return merge(left, right)

def merge(left, right):
    leftI = rightI = 0
    merged = []
    
    while (leftI < len(left) and rightI < len(right)):
        if left[leftI] < right[rightI]:
            merged.append(left[leftI])
            leftI += 1
        else:
            merged.append(right[rightI])
            rightI += 1
    
    merged.extend(left[leftI:])
    merged.extend(right[rightI:])
    
    return merged

if __name__ == '__main__':
    arr = [1,2,5,5,9,22,6,3,6,8,1,43,5]
    print(merge_sort(arr))

出于某种原因，我获得了：

[1, 2, 5, 5, 6, 3, 6, 8, 1, 9, 22, 43, 5]

有效实施（从朋友那里得到）：

def merge_sort(list):
    list_length = len(list)

    if list_length == 1:
        return list

    mid_point = list_length // 2

    left_partition = merge_sort(list[:mid_point])
    right_partition = merge_sort(list[mid_point:])

    return merge(left_partition, right_partition)


def merge(left, right):
    output = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            output.append(left[i])
            i += 1
        else:
            output.append(right[j])
            j += 1
            
    output.extend(left[i:])
    output.extend(right[j:])

    return output

if __name__ == '__main__':
    arr = [1,2,5,5,9,22,6,3,6,8,1,43,5]
    print(merge_sort(arr))

此代码产生：

[1, 1, 2, 3, 5, 5, 5, 6, 6, 8, 9, 22, 43]

我就是想不通出了什么问题。如果有人能花点时间帮助我，那将是一个很大的帮助:)

Answer 1

在您的 merge_sort 函数中，您不会根据 merge_sort returns 更改 left 和 right 的值。你有：

merge_sort(left)
merge_sort(right)

它应该在哪里：

left = merge_sort(left)
right = merge_sort(right)

有人可以帮我弄清楚我的合并排序实现有什么问题吗？

Can someone help me to figure out what's wrong in my implementation of merge sort?

sorting

mergesort

python-3.x