难以理解在合并排序算法中实际创建了多少数组
Having trouble understanding how many arrays are actually created in the merge sort algorithm
我一直在研究合并排序算法，但我无法断定作为该算法的一部分实际创建了多少数组。某些文献说整个原始数组被复制到一个经过排序的新数组中。但这意味着只创建了 2 个数组。
据我了解，归并排序算法有两个主要步骤。分裂与合并。我想如果你给合并排序一个 100 个槽的数组，它实际上会创建新的数组，因为它从中间分裂 100 > 50/50 > 25/25 > 12/13 > 6/5 > 3/3 > 1/1 .在所有这些拆分之后，它在内存中有 12 或 13 个数组。然后当它最终将所有这些复制到 1 > 2 > 3 或 4 > 6 > 12 > 25 > 50 > 100 的新数组中时。
那是另外 8 个数组（粗略地说）。
但在教科书上我读到的是这样的：
You may wonder where all these subarrays are located in memory. In the
algorithm, a workspace array of the same size as the original array is
created. The subarrays are stored in sections of the workspace array.
This means that subarrays in the original array are copied to
appropriate places in the workspace array. After each merge, the
workspace array is copied back into the original array.
-- Java 中的数据结构和算法，作者：Robert Lafore
即使您 "split" 您的阵列，您也不必创建 2 个新阵列。
你总是有相同数量的插槽（这里是 100，即使它是 50*2 或 25*4...）
您只需将数据移动到数组中的正确位置（第一次拆分后，前 50 个槽是第一个数组，后 50 个槽是第二个数组）
您不必存储数组，只需存储它们在大数组中起始位置的索引。
考虑典型归并排序实现的两个最后阶段。我们需要两个数组——主数组和辅助数组，并将子数组从辅助数组合并到主数组。
在某个合并阶段之前（| 表示每个数组片段的开始（起始索引））——我们将 A 子数组与 B 子数组合并以填充目标数组的前半部分，并将 C 子数组与 D 合并填充目标数组后半部分的子数组：
Auxiliary array: |AAAA|BBBB|CCCC|DDDD
Main array: ..................
合并后（我使用任意排序）
Auxiliary array: ...............
Main array: ABBABBAADCDDCCDC
复制后，最终合并前
Auxiliary array: |ABBABBAA|DCDDCCDC
Main array: ................
教科书指的是相当有效的合并实现，其中完成了与原始大小相同的工作区数组的一次性分配。在那之后，所有要合并的子数组都是工作区数组或原始数组的一部分，通过索引（或指针）访问。
自上而下的合并排序使用递归生成索引对的动态堆栈来表示子数组。自底向上合并排序跳过递归，并使用迭代生成索引，从子数组大小 1 开始。
我一直在研究合并排序算法，但我无法断定作为该算法的一部分实际创建了多少数组。某些文献说整个原始数组被复制到一个经过排序的新数组中。但这意味着只创建了 2 个数组。
据我了解，归并排序算法有两个主要步骤。分裂与合并。我想如果你给合并排序一个 100 个槽的数组，它实际上会创建新的数组，因为它从中间分裂 100 > 50/50 > 25/25 > 12/13 > 6/5 > 3/3 > 1/1 .在所有这些拆分之后，它在内存中有 12 或 13 个数组。然后当它最终将所有这些复制到 1 > 2 > 3 或 4 > 6 > 12 > 25 > 50 > 100 的新数组中时。
那是另外 8 个数组（粗略地说）。
但在教科书上我读到的是这样的：
You may wonder where all these subarrays are located in memory. In the algorithm, a workspace array of the same size as the original array is created. The subarrays are stored in sections of the workspace array. This means that subarrays in the original array are copied to appropriate places in the workspace array. After each merge, the workspace array is copied back into the original array.
-- Java 中的数据结构和算法，作者：Robert Lafore
即使您 "split" 您的阵列，您也不必创建 2 个新阵列。 你总是有相同数量的插槽（这里是 100，即使它是 50*2 或 25*4...）
您只需将数据移动到数组中的正确位置（第一次拆分后，前 50 个槽是第一个数组，后 50 个槽是第二个数组）
您不必存储数组，只需存储它们在大数组中起始位置的索引。
考虑典型归并排序实现的两个最后阶段。我们需要两个数组——主数组和辅助数组，并将子数组从辅助数组合并到主数组。
在某个合并阶段之前（| 表示每个数组片段的开始（起始索引））——我们将 A 子数组与 B 子数组合并以填充目标数组的前半部分，并将 C 子数组与 D 合并填充目标数组后半部分的子数组：
Auxiliary array: |AAAA|BBBB|CCCC|DDDD
Main array: ..................
合并后（我使用任意排序）
Auxiliary array: ...............
Main array: ABBABBAADCDDCCDC
复制后，最终合并前
Auxiliary array: |ABBABBAA|DCDDCCDC
Main array: ................
教科书指的是相当有效的合并实现，其中完成了与原始大小相同的工作区数组的一次性分配。在那之后，所有要合并的子数组都是工作区数组或原始数组的一部分，通过索引（或指针）访问。
自上而下的合并排序使用递归生成索引对的动态堆栈来表示子数组。自底向上合并排序跳过递归，并使用迭代生成索引，从子数组大小 1 开始。