就地合并过程：

Question

MergeSort中的合并过程无法就地运行。这是我的解释：

加起来吗？

A = 5,1,9,2,10,0

“ q”：指向索引2处数组中间的指针。

我们正在合并q及其左侧的元素与q右侧的元素。

A = 1,5,10,0,2,12

我们用“ i”指向左侧的开头，而用“ j”指向右侧的开头。

我们用“ k”指向数组中的当前位置。

该算法以i = 0，j = 3，k = 0开头。

如果我们在原处合并：对于k = 0：i = 0，j = 3,0 <1-> A [k] = A [j] andj ++

结果数组：A = {0,5,10,0,2,12}

我们可以看到，我们已经丢失了值1。

例如，在下一次迭代中，我们将继续失去价值：

对于k = 1：i = 0，j = 4,0 <2 =⇒A[k] = A [i] andi + +

结果数组：A = {0,0,10,0,2,12}

Answer 1

可以通过旋转子阵列来完成。存在具有O（n log（n））时间复杂度的合并排序，但是这些排序将数组的一部分用作工作存储。如果需要稳定性，则使用一小部分唯一值（例如2 sqrt（n））来提供空间，因为在排序之前对唯一值进行重新排序不会破坏稳定性。回到简单的旋转算法：

 1  5 10  0  2 12
 0  1  5 10  2 12         0 <  1, rotate  0 into place, adjust working indexes
 0  1  5 10  2 12         1 <  2, continue
 0  1  2  5 10 12         2 <  5, rotate  2 into place, adjust working indexes
 0  1  2  5 10 12         5 < 12, continue
 0  1  2  5 10 12        10 < 12, continue, end of left run, done