为什么标准的合并排序没有到位？

Question

在归并排序的归并算法中，我不明白我们必须使用辅助数组L，R？为什么我们不能只保留 2 个指针对应我们在 2 个子数组 L 和 R 中比较的元素，以便合并排序算法保持不变？

谢谢。

Answer 1

假设你分割了你的数组。L 使用原始数组的前半部分，R 使用后半部分。

然后说在合并过程中，R 中的前几个元素小于 L 中的最小元素。如果要将它们放在合并结果的正确位置，则必须覆盖 L 中在合并期间尚未处理的元素还没迈出一步。

当然你可以进行不同的分割。但你总是可以构造这样一个（然后略有不同）的例子。