Python 中高效的合并排序实现

Question

def merge(arr, l, m, r):
    merged_arr = []
    i, j = 0, 0
    while (i < len(arr[l:m])) and (j < len(arr[m:r+1])):
        if arr[l+i] < arr[m+j]:
            merged_arr.append(arr[l+i])
            i += 1
        elif arr[l+i] >= arr[m+j]:
            merged_arr.append(arr[m+j])
            j += 1
    merged_arr.extend(arr[m+j:r+1])
    merged_arr.extend(arr[l+i:m])
    arr[l:r+1] = merged_arr
    return

def merge_sort(arr, l, r):
    if r > l:
        m = (l + r) // 2
        merge_sort(arr, l, m)
        merge_sort(arr, m+1, r)
        return merge(arr, l, m, r)

我不确定我的

merge

功能出了什么问题。以下效果很好：

print(merge([1,4,7,8,9,20,  0,4,5,15,67,68], 0, 6,12))

但是，这不会给出正确的输出：

print(merge_sort([1, 5, 4, 2, 33, 4, 2, 44, 22, 0], 0, 10))

Answer 1

不包含切片的结束索引：

def merge(arr, l, m, r):
    L, R, i, j = arr[l:m], arr[m:r], 0, 0
    merged_arr = []
    while i < len(L) and j < len(R):
        if L[i] < R[j]:
            merged_arr.append(L[i])
            i += 1
        else:
            merged_arr.append(R[j])
            j += 1
    merged_arr.extend(L[i:])
    merged_arr.extend(R[j:])
    arr[l:r] = merged_arr


def merge_sort(arr, l, r):
    if r - l > 1:
        m = (l + r) // 2
        merge_sort(arr, l, m)
        merge_sort(arr, m, r)
        merge(arr, l, m, r)


A = [1, 5, 4, 2, 33, 4, 2, 44, 22, 0]
merge_sort(A, 0, len(A))
print(A)

打印

[0, 1, 2, 2, 4, 4, 5, 22, 33, 44]