python - 如何提高 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

使用

while True:

代替

while len(left) > left_count and len(right) > right_count:

让我的速度提高了 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:]

最后一行似乎并没有让它变得更快，但我更喜欢它。