python - 为什么我不能以这种方式实现合并排序

Question

我理解合并排序的工作原理是分而治之，你一直减半，直到达到可以在恒定时间内排序的点，或者列表只是一个元素，然后你合并列表。

def mergesort(l):
    if len(l)<=1:
        return l
    l1 = l[0:len(l)//2+1]
    l2 = l[len(l)//2:]

    l1 = mergesort(l1)
    l2 = mergesort(l2)

    return merge(l1,l2)

我有一个有效的合并实现，我检查它工作正常，但合并排序实现不起作用，它只返回列表的一半元素。

我在 Internet 上看到合并排序是使用 l & r 和 m = (l + r)/2 实现的。我的实现有什么问题？我正在递归地分割列表并合并。

Answer 1

问题是代码中的 +1，这里:

l1 = l[0:len(l)//2]
l2 = l[len(l)//2:]

用你的代码替换它就可以了