我试图从直觉上理解，合并排序的运行时如何比插入排序好得多。
即使我们通过合并排序进行分而治之，但在单个CPU上，合并排序执行树的每个节点都将顺序执行。 每个递归调用（迭代）上较小的输入大小是否是合并排序的关键？]] >> 还是这样的事实，因为合并排序不是就地且使用O（n）空间，这节省了我们在插入排序中必须做的移位次数，以便为较小的数字插入空间。 但是在每个合并步骤中复制左右临时数组中的元素的代价如何呢？
我试图从直觉上理解，合并排序的运行时如何比插入排序好得多。即使我们使用合并排序进行分治，但在单个CPU上，每个...
是的，与插入排序相比，较小的输入大小大部分来自合并排序的加快。 mergesort使用更多空间的事实更多地是它如何工作的产物，而不是加速的内在原因。
这里是一种查看方式。我们知道插入排序平均花费时间Θ（n 2
即使在典型的X86上，n> =〜128，就地合并排序（O（1）空间）也比插入排序要快。