对于初学者： 我无法在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
