与插入排序相比，合并排序本质上是以 space 换取时间吗
Does merge sort essentially trade space for time when compared to insertion sort
我试图从直觉上理解合并排序的运行时间为何比插入排序好得多。
即使我们用归并排序分而治之，在单个 CPU 上，归并排序执行树的每个节点都将串行执行。 每次递归调用（迭代）时较小的输入大小是归并排序的关键吗？
或者是因为归并排序不是原位的并且使用 O(n) space 这节省了我们在插入排序中必须做的轮班次数make space 用于插入较小的数字。
但是在每个合并步骤中复制左右临时数组中的元素的惩罚呢？
即使是就地归并排序 (O(1) space) 也比典型 X86 上 n >= ~128 的插入排序快。
对于较小的 n，由于缓存和相关常数因素，插入排序速度更快，因此，稳定排序的大多数库实现使用插入排序（创建小的排序运行）和自下而上合并的混合排序。
就地合并排序的一个示例是块合并排序 (grail)，O(1) space，仍然具有 O(n log(n)) 时间复杂度，但比慢了大约 50%标准归并排序，代码复杂：
https://github.com/Mrrl/GrailSort/blob/master/GrailSort.h
But what about the penalty of copying the elements in left and right temporary arrays in every merge step?
典型的合并排序通过一次性分配临时数组来避免数据复制，然后根据自下而上合并排序的合并传递或自上而下合并排序的递归级别更改合并方向。
是的，与插入排序相比，归并排序的加速主要来自较小的输入大小。 mergesort 使用更多 space 的事实与其说是加速的内在原因，不如说是它如何工作的产物。
这是一种查看方式。我们知道，插入排序平均耗时 Θ(n2)。现在，假设您要对包含 n 个元素的数组进行插入排序。相反，您将数组分成两个大小约为 n/2 的较小数组，并对每个数组进行插入排序。这需要多长时间？由于插入排序的运行时间是二次方的，因此每半个插入排序的成本大约是对整个数组进行插入排序成本的四分之一 ((n/2)2 = n2 / 4).由于有两个这样的数组，以这种方式排序的总成本大约是
2(n2 / 4) = n2 / 2,
这是对原始数组进行排序所需时间的一半。这产生了一种简单的排序算法，它是对插入排序的改进：
- 将数组分成两半。
- 插入排序每半。
- 将两半合并在一起。
最后一步引入了合并的线性 space 开销，尽管您可以以更高的成本使用就地合并来完成。
这种算法“拆分排序”的速度大约是插入排序的两倍。那么你可能会问 - 为什么分成两半？为什么不是宿舍？毕竟对四分之一的数组进行排序的开销大约是
(n/4)2 = n2 / 16,
比原数组排序快十六倍！我们可以把它变成这样的排序算法：
- 将数组分成四等份。
- 每季度插入排序。
- 将宿舍合并成两半。
- 将两半合并到完整数组中。
这将比插入排序快四倍左右（每次排序花费原始排序时间的十六分之一，我们做了四次）。
您可以将合并排序视为此过程的“极限”，我们从不停止拆分并将数组划分为尽可能小的单元，然后在最后将它们全部合并回一起。加速是基于这样一个事实，即对较小的数组进行排序本质上比对较大的数组进行排序更快，合并的内存开销更多是一个实现细节，而不是加速的内在原因。
另一种证明 space 用法对于加速不是必需的方法是比较插入排序和堆排序。 Heapsort 也在时间 O(n log n) 中运行，但仅使用 O(1) 辅助 space.
希望对您有所帮助！
我试图从直觉上理解合并排序的运行时间为何比插入排序好得多。
即使我们用归并排序分而治之，在单个 CPU 上，归并排序执行树的每个节点都将串行执行。 每次递归调用（迭代）时较小的输入大小是归并排序的关键吗？
或者是因为归并排序不是原位的并且使用 O(n) space 这节省了我们在插入排序中必须做的轮班次数make space 用于插入较小的数字。
但是在每个合并步骤中复制左右临时数组中的元素的惩罚呢？
即使是就地归并排序 (O(1) space) 也比典型 X86 上 n >= ~128 的插入排序快。
对于较小的 n，由于缓存和相关常数因素，插入排序速度更快，因此，稳定排序的大多数库实现使用插入排序（创建小的排序运行）和自下而上合并的混合排序。
就地合并排序的一个示例是块合并排序 (grail)，O(1) space，仍然具有 O(n log(n)) 时间复杂度，但比慢了大约 50%标准归并排序，代码复杂：
https://github.com/Mrrl/GrailSort/blob/master/GrailSort.h
But what about the penalty of copying the elements in left and right temporary arrays in every merge step?
典型的合并排序通过一次性分配临时数组来避免数据复制，然后根据自下而上合并排序的合并传递或自上而下合并排序的递归级别更改合并方向。
是的，与插入排序相比，归并排序的加速主要来自较小的输入大小。 mergesort 使用更多 space 的事实与其说是加速的内在原因，不如说是它如何工作的产物。
这是一种查看方式。我们知道，插入排序平均耗时 Θ(n2)。现在，假设您要对包含 n 个元素的数组进行插入排序。相反，您将数组分成两个大小约为 n/2 的较小数组，并对每个数组进行插入排序。这需要多长时间？由于插入排序的运行时间是二次方的，因此每半个插入排序的成本大约是对整个数组进行插入排序成本的四分之一 ((n/2)2 = n2 / 4).由于有两个这样的数组，以这种方式排序的总成本大约是
2(n2 / 4) = n2 / 2,
这是对原始数组进行排序所需时间的一半。这产生了一种简单的排序算法，它是对插入排序的改进：
- 将数组分成两半。
- 插入排序每半。
- 将两半合并在一起。
最后一步引入了合并的线性 space 开销，尽管您可以以更高的成本使用就地合并来完成。
这种算法“拆分排序”的速度大约是插入排序的两倍。那么你可能会问 - 为什么分成两半？为什么不是宿舍？毕竟对四分之一的数组进行排序的开销大约是
(n/4)2 = n2 / 16,
比原数组排序快十六倍！我们可以把它变成这样的排序算法：
- 将数组分成四等份。
- 每季度插入排序。
- 将宿舍合并成两半。
- 将两半合并到完整数组中。
这将比插入排序快四倍左右（每次排序花费原始排序时间的十六分之一，我们做了四次）。
您可以将合并排序视为此过程的“极限”，我们从不停止拆分并将数组划分为尽可能小的单元，然后在最后将它们全部合并回一起。加速是基于这样一个事实，即对较小的数组进行排序本质上比对较大的数组进行排序更快，合并的内存开销更多是一个实现细节，而不是加速的内在原因。
另一种证明 space 用法对于加速不是必需的方法是比较插入排序和堆排序。 Heapsort 也在时间 O(n log n) 中运行，但仅使用 O(1) 辅助 space.
希望对您有所帮助！