我一直在阅读 Sedgewick & Wayne 的“Algorithms, 4th Ed”，并且在此过程中我一直在实现 JavaScript 中讨论的算法。
我最近采用了书中提供的合并排序示例来比较自上而下和自下而上的方法……但我发现自下而上的运行速度更快（我认为）。在我的博客上查看我的分析。- http://www.akawebdesign.com/2012/04/13/javascript-mergesort-top-down-vs-bottom-up/
我还没有找到任何讨论说一种合并排序方法应该比另一种更快。我的实施（或分析）有缺陷吗？
注意：我的分析测量算法的迭代循环，而不是严格的数组比较/移动。也许这是有缺陷或无关紧要的？
编辑：我的分析实际上并没有计时速度，所以我关于它运行“更快”的说法有点误导。我正在通过递归方法（自上而下）和 for 循环（自下而上）跟踪“迭代”——自下而上似乎使用较少的迭代。
我还没有找到任何讨论说一种合并排序方法应该比另一种更快。
自下而上和自上而下的合并排序以及其他变体在 90 年代已得到很好的研究。简而言之，如果以单个key的比较次数来衡量成本，最好的成本相同（~（n lg n）/2），自顶向下的最差成本低于或等于最差自下而上的情况（但都〜n lg n）和自上而下的平均成本低于或等于自下而上的平均情况（但都〜n lg n），其中“lg n”是二进制对数。差异源于线性项。当然，如果n=2^p，这两种变体其实是完全一样的。这意味着，比较而言，自上而下总是比自下而上好。进一步证明了自顶向下归并排序的“半半”分裂策略是最优的。研究论文来自 Flajolet、Golin、Panny、
以下是我在 Erlang 的书Design and Analysis of Purely Functional Programs（College Publications，UK）中提出的内容：
tms([X|T=[_|U]]) -> cutr([X],T,U);
tms(T) -> T.
cutr(S,[Y|T],[_,_|U]) -> cutr([Y|S],T,U);
cutr(S, T, U) -> mrg(tms(S),tms(T)).
mrg( [], T) -> T;
mrg( S, []) -> S;
mrg(S=[X|_],[Y|T]) when X > Y -> [Y|mrg(S,T)];
mrg( [X|S], T) -> [X|mrg(S,T)].
请注意，这不是一个稳定的排序。此外，在 Erlang（和 OCaml）中，如果要节省内存，则需要在模式中使用别名(ALIAS=...)。这里的诀窍是在不知道其长度的情况下找到列表的中间位置。这是由 cutr/3 完成的，它处理两个指向输入列表的指针：一个增加一，另一个增加二，所以当第二个到达末尾时，第一个在中间。（我从 Olivier Danvy 的一篇论文中了解到这一点。）这样，您不需要跟踪长度，也不需要复制列表后半部分的单元格，因此您只需要 (1/2 )n lg n 额外空间，与 n lg n。这不是众所周知的。
人们经常声称自下而上的变体更适合函数式语言或链表（Knuth、Panny、Prodinger），但我认为这不是真的。
由于缺乏关于归并排序的讨论，我和你一样感到困惑，所以我做了自己的研究并写了一大章。我目前正在准备一个新版本，其中包含更多关于合并排序的材料。
顺便说一句，还有其他变体：队列合并排序和在线合并排序（我在书中讨论了后者）。
[编辑：由于成本的衡量标准是比较次数，因此选择数组与链表之间没有区别。当然，如果你用链表实现自上而下的变体，你必须很聪明，因为你不一定知道键的数量，但你每次都需要遍历至少一半的键，并且重新分配总共 (1/2)n lg n 个单元格（如果你很聪明的话）。使用链表的自下而上合并排序实际上需要更多额外的内存，n lg n + n 个单元格。因此，即使使用链表，自上而下的变体也是最佳选择。就程序的长度而言，您的里程可能会有所不同，但在函数式语言中，如果不需要稳定性，自顶向下的合并排序可以比自底向上的排序更短。有一些论文讨论了合并排序的实现问题，合并排序程序的细致分析，Katajainen 和 Larsson Traff (1997)。]
我曾在本课程2012 年 8 月版的 coursera 课堂论坛上问过同样的问题。普林斯顿大学的 Kevin wayne 教授回答说，在许多情况下，递归比迭代更快，因为缓存提高了性能。
所以我当时得到的简短回答是，由于缓存原因，自上而下的合并排序将比自下而上的合并排序更快。
请注意，该课程是用 Java 编程语言（不是 Javascript）教授的。
如果更快意味着更少的“迭代”，那么是的。如果您想知道执行时间。
原因是这 21,513 次迭代中的一些迭代次数超过了 22,527 次迭代。
从源代码来看，您的图表中的一些叶节点似乎是一起排序的，而不是单独排序，导致合并和排序更少，但它们花费的时间更长。