python - 使用 Python 进行合并排序

Question

我找不到任何有效的Python 3.3归并排序算法代码，所以我自己做了一个。有什么办法可以加快速度吗？它在大约 0.3-0.5 秒内对 20,000 个数字进行排序

def msort(x):
    result = []
    if len(x) < 2:
        return x
    mid = int(len(x)/2)
    y = msort(x[:mid])
    z = msort(x[mid:])
    while (len(y) > 0) or (len(z) > 0):
        if len(y) > 0 and len(z) > 0:
            if y[0] > z[0]:
                result.append(z[0])
                z.pop(0)
            else:
                result.append(y[0])
                y.pop(0)
        elif len(z) > 0:
            for i in z:
                result.append(i)
                z.pop(0)
        else:
            for i in y:
                result.append(i)
                y.pop(0)
    return result

Answer 1

第一个改进是简化主循环中的三种情况:不是在某些序列具有元素时进行迭代，而是在两个序列都具有元素时进行迭代。当离开循环时，其中一个将为空，我们不知道是哪一个，但我们不在乎:我们将它们附加在结果的末尾。

def msort2(x):
    if len(x) < 2:
        return x
    result = []          # moved!
    mid = int(len(x) / 2)
    y = msort2(x[:mid])
    z = msort2(x[mid:])
    while (len(y) > 0) and (len(z) > 0):
        if y[0] > z[0]:
            result.append(z[0])
            z.pop(0)
        else:
            result.append(y[0])
            y.pop(0)
    result += y
    result += z
    return result

第二个优化是避免 popping 元素。相反，有两个索引:

def msort3(x):
    if len(x) < 2:
        return x
    result = []
    mid = int(len(x) / 2)
    y = msort3(x[:mid])
    z = msort3(x[mid:])
    i = 0
    j = 0
    while i < len(y) and j < len(z):
        if y[i] > z[j]:
            result.append(z[j])
            j += 1
        else:
            result.append(y[i])
            i += 1
    result += y[i:]
    result += z[j:]
    return result

最后的改进在于使用非递归算法对短序列进行排序。在本例中，我使用内置的 sorted 函数，并在输入大小小于 20 时使用它:

def msort4(x):
    if len(x) < 20:
        return sorted(x)
    result = []
    mid = int(len(x) / 2)
    y = msort4(x[:mid])
    z = msort4(x[mid:])
    i = 0
    j = 0
    while i < len(y) and j < len(z):
        if y[i] > z[j]:
            result.append(z[j])
            j += 1
        else:
            result.append(y[i])
            i += 1
    result += y[i:]
    result += z[j:]
    return result

我对 100000 个整数的随机列表进行排序的测量结果是，原始版本为 2.46 秒，msort2 为 2.33 秒，msort3 为 0.60 秒，msort4 为 0.40 秒。作为引用，使用 sorted 对所有列表进行排序需要 0.03 秒。