如何提高python中的合并排序速度

Question

是的，这是家庭作业，但我最终还是用Java来完成它，但是现在python的实现让我很困扰。我很确定我已经正确地实现了它，但是它需要的时间比它应该的要长。在300万个输入信号的情况下，它可以在25秒到32秒的任何地方进行。我想这和我拼接的方式有关，然后把它附加到列表中。我有源代码在这里，如果你看到什么让我知道。在

def merge_sort(seq):
    if len(seq) == 1:
        return seq
    left = merge_sort(seq[:len(seq) // 2])
    right = merge_sort(seq[len(seq) // 2:])

    return merge(left, right)


def merge(left, right):
    result = []
    left_count = 0
    right_count = 0
    while len(left) > left_count and len(right) > right_count:
        if left[left_count] > right[right_count]:
            result.append(right[right_count])
            right_count += 1
        else:
            result.append(left[left_count])
            left_count += 1

    while len(left) > left_count:
        result.append(left[left_count])
        left_count += 1

    while len(right) > right_count:
        steps += 1
        result.append(right[right_count])
        right_count += 1

    return result

Answer 1

来自Rishav Kundu链接到的前一个线程：

---

您可以在mergesort的顶层调用中初始化整个结果列表：

result = [0]*len(x)   # replace 0 with a suitable default element if necessary. 
                      # or just copy x (result = x[:])

然后，对于递归调用，您可以使用一个helper函数，而不是向其传递子列表，而是将索引传递到x。底层调用从x读取它们的值，并直接写入result。在

---

为了实现这一点，seq数组的参数需要是对seq的引用，同时也是helper数组的引用。在

还可以添加一个参数来跟踪要合并的方向，这样就避免了“复制回”步骤。C示例使用mtoa标志表示从b到a的合并（如果为false，则表示合并a到b）。在我的系统intel2600k3.4ghz上，这段代码在0.36秒内对400万个32位无符号伪随机整数进行排序，在1.6秒内对1600万个进行排序。在

^{pr2}$

另一个选择是使用自底向上的合并排序，它跳过递归步骤，只开始将偶数运行与奇数运行合并，初始运行大小为1。在

Answer 2

我认为你是对的。切片创建一个包含切片元素的新列表。这必然是一项耗资巨大的行动。在

在Java中，没有通用的切片特性。但是，如果您使用List.subList，它将返回原始视图而不是副本，我认为速度会快得多。就地阵列操作，会更快。在

Answer 3

使用

while True:

而不是

^{pr2}$

让我快了40-45%：

def merge(left, right):
    result = []
    left_count = 0
    right_count = 0
    try:
        while True:
            if left[left_count] > right[right_count]:
                result.append(right[right_count])
                right_count += 1
            else:
                result.append(left[left_count])
                left_count += 1
    except:
        return result + left[left_count:] + right[right_count:]

最后一行似乎没有加快速度，但我更喜欢它。在