假设我有一个未排序的数组p，它的排序等价于p_sorted。假设L和R指的是P的左半部分和右半部分。有没有一种方法可以在线性时间内从P和P_Sorted中恢复L_Sorted和R_Sorted而不使用额外的内存？
为了进一步说明，在递归合并排序实现过程中，L_Sorted和R_Sorted将合并在一起形成p_Sorted，所以我有点想反转合并步骤。
在合并排序中，您可以递归地将数组分成两半并合并它们。所以在最后一次合并时，您已经对左半部分和右半部分进行了排序——它们是独立排序的——这就是为什么要使用分治名称。
因此，在进行合并时，您只需查看要合并的数组的大小，如果它们相等(偶数输入大小(或相差1(奇数输入大小(，则表示您处于最后一次合并。然后，您可以在合并之前将这些排序后的数组存储在某个变量中。
但是 如果不允许您处理函数，并且您只需要处理排序的数组和原始数组，我认为解决方案并不简单。我找到了一个url，提出了这个问题和可能的解决方案。
对于非常特定的数据集，它在线性时间内似乎是可行的：
如果有一种方法可以告诉排序列表中每个数据元素的原始位置，例如，如果这些是具有创建日期和名称字段的记录，并且原始数组是按时间顺序排列的，则可以在线性时间内的一次扫描中选择位于前半部分或后半部分的元素，而无需空间开销。
在一般情况下，对左半部分和右半部分进行排序似乎是获得L_sorted和R_sorted的最有效方法，无论是否使用P_sorted。时间复杂度为O(n.log(n((。