对于初学者： 我无法在100个周期和大小为10000 的
列表上重现您的计时结果。timeit此答案中讨论的所有实现（包括Bubblesort 和
您的原始代码段）的详尽基准测试都作为要点在此处发布。对于单次运行的平均持续时间，我发现以下结果：

• Python的本机（Tim）排序：0.0144600081444
• 泡泡排序：26.9620819092
• （您的）原始合并排序：0.224888720512

现在，为了使您的功能更快，您可以做一些事情。

• 编辑 ：好吧，显然，我错了（感谢cwillu）。长度计算在python中采用O（1）。但是到处删除无用的计算仍然会改善一些情况（原始Mergesort：0.224888720512，无长度Mergesort：0.195795390606）：

        def nolenmerge(array1,array2):
        merged_array=[]
        while array1 or array2:
            if not array1:
                merged_array.append(array2.pop(0))
            elif (not array2) or array1[0] < array2[0]:
                merged_array.append(array1.pop(0))
            else:
                merged_array.append(array2.pop(0))
        return merged_array

    def nolenmergeSort(array):
        n  = len(array)
        if n <= 1:
            return array
        left = array[:n/2]
        right = array[n/2:]
        return nolenmerge(nolenmergeSort(left),nolenmergeSort(right))

• 其次，如该答案所示，它 pop(0) 是线性的。将合并重写到pop()最后：

        def fastmerge(array1,array2):
        merged_array=[]
        while array1 or array2:
            if not array1:
                merged_array.append(array2.pop())
            elif (not array2) or array1[-1] > array2[-1]:
                merged_array.append(array1.pop())
            else:
                merged_array.append(array2.pop())
        merged_array.reverse()
        return merged_array

这又是更快：无镜头合并：0.195795390606，无镜头合并+快速合并：0.126505711079

• 第三- 仅当您使用的是进行尾部调用优化的语言时，这才是有用的 ，没有它，这是一个坏主意 -合并到的调用merge不是尾部递归的；它同时呼吁(mergeSort left)和(mergeSort right)递归同时有呼叫剩下的工作(merge)。

但是，您可以使用CPS进行合并尾递归（如果不执行tco，即使是适度的列表也将耗尽堆栈大小）：

        def cps_merge_sort(array):
        return cpsmergeSort(array,lambda x:x)

    def cpsmergeSort(array,continuation):
        n  = len(array)
        if n <= 1:
            return continuation(array)
        left = array[:n/2]
        right = array[n/2:]
        return cpsmergeSort (left, lambda leftR:
                             cpsmergeSort(right, lambda rightR:
                                          continuation(fastmerge(leftR,rightR))))

完成此操作后，您可以 手工 执行TCO ，
以将通过递归完成的调用堆栈管理推迟到正常功能的while循环中（蹦床，例如，此处进行了解释，最初是由Guy
Steele造成的）。 Trampolining和CPS可以很好地合作 。

您编写了一个thunk函数，该函数“记录”并延迟了应用程序：它接受一个函数及其参数，然后返回一个函数，该函数返回（该原始函数应用于这些参数）。

    thunk = lambda name, *args: lambda: name(*args)

然后，您编写一个蹦床来管理对thunk的调用：它将应用thunk，直到thunk返回结果（而不是另一个thunk）

    def trampoline(bouncer):
    while callable(bouncer):
        bouncer = bouncer()
    return bouncer

然后剩下的就是从原始CPS函数“冻结”（thunk）所有递归调用，以使蹦床按正确的顺序解开它们。现在，您的函数在每次调用时都返回一个thunk，而不进行递归（并丢弃其自己的帧）：

        def tco_cpsmergeSort(array,continuation):
        n  = len(array)
        if n <= 1:
            return continuation(array)
        left = array[:n/2]
        right = array[n/2:]
        return thunk (tco_cpsmergeSort, left, lambda leftR:
                      thunk (tco_cpsmergeSort, right, lambda rightR:
                             (continuation(fastmerge(leftR,rightR)))))

    mycpomergesort = lambda l: trampoline(tco_cpsmergeSort(l,lambda x:x))

不幸的是，这 进展得不 那么快
（递归mergesort：0.126505711079，此修订版本：0.170638551712）。好的，我猜想
递归合并排序算法的堆栈膨胀实际上是适度的
：只要您离开数组切片递归模式中最左边的路径，该算法就会开始返回（并删除帧）。因此，对于10K大小的列表，您获得的函数堆栈最多为log_2（10000）=14 …相当适中。

您可以以此SO回答的名义做一些涉及堆栈式TCO消除的工作：

    def leftcomb(l):
        maxn,leftcomb = len(l),[]
        n = maxn/2
        while maxn > 1:
            leftcomb.append((l[n:maxn],False))
            maxn,n = n,n/2
        return l[:maxn],leftcomb

    def tcomergesort(l):
        l,stack = leftcomb(l)
        while stack: # l sorted, stack contains tagged slices
            i,ordered = stack.pop()
            if ordered:
                l = fastmerge(l,i)
            else:
                stack.append((l,True)) # store return call
                rsub,ssub = leftcomb(i)
                stack.extend(ssub) #recurse
                l = rsub
        return l

但这 只会加快一点点的速度（trampolinedmergesort：0.170638551712，此基于堆栈的版本：0.144994809628）。显然，在原始合并类型的递归调用中，构建堆栈的python相当便宜。

最终结果？在我的机器上（Ubuntu natty的股票Python 2.7.1+），平均运行时间（在100次运行中-
除Bubblesort外，列表大小为10000，包含大小为0-10000000的随机整数）为：

• Python的本机（Tim）排序：0.0144600081444
• 泡泡排序：26.9620819092
• 原始合并排序：0.224888720512
• 无镜头合并排序：0.195795390606
• 无镜头合并+快速合并：0.126505711079
• 践踏CPS Mergesort + fastmerge：0.170638551712
• 基于堆栈的mergesort + fastmerge：0.144994809628