我一直在研究合并排序算法，但我无法断定作为该算法的一部分实际创建了多少数组。某些文献说整个原始数组被复制到一个经过排序的新数组中。但这意味着只创建了 2 个数组。
据我了解，归并排序算法有两个主要步骤。 split 与合并。我想如果你给合并排序一个 100 个槽的数组，它实际上会创建新的数组，因为它从中间 split 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
最佳答案
考虑典型归并排序实现的两个最后阶段。我们需要两个数组 - 主数组和辅助数组，并将子数组从辅助数组合并到主数组。
在某些合并阶段之前(| 表示每个数组片段的开始(起始索引))——我们将 A 子数组与 B 子数组合并以填充目标数组的前半部分，并将 C 子数组与D 子数组填充目标数组的后半部分:
Auxiliary array: |AAAA|BBBB|CCCC|DDDD
Main array: ..................
合并后(我使用任意排序)
Auxiliary array: ...............
Main array: ABBABBAADCDDCCDC
复制后，最终合并前
Auxiliary array: |ABBABBAA|DCDDCCDC
Main array: ................
关于algorithm - 难以理解在合并排序算法中实际创建了多少数组，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36160195/