优化原地归并排序：实现 O(1) 空间复杂度
在 88. Merge Sorted Array 中，因为 nums1 预留了空间
（Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3）
，相当于用了额外空间，使得我们能够直接向尾部插入大元素原地排序：
1 void merge(vector<int> &v1, int m, vector<int> &v2, int n) {
2 int l = m - 1, r = n - 1, ins = m + n - 1; // ins: 插入位置
3 while (l >= 0 && r >= 0) {
4 if (v1[l] > v2[r]) {
5 v1[ins] = v1[l];
6 ins--;
7 l--;
8 } else {
9 v1[ins] = v2[r];
10 ins--;
11 r--;
12 }
13 }
14 while (r >= 0) {
15 v1[ins] = v2[r];
16 ins--;
17 r--;
18 }
19 }
然而在实际情况，我们面临的是这样的数组：
arr = [...2,5,6,1,2,3...]
^ ^ ^ ^
l1 m l2 r
按照上面的算法：
// 比较 6 > 3，因此尾部插入 6 被覆盖
arr = [...2,5,6,1,2,6...]
^ ^ ^ ^
l1 m l2 r
出问题了，3 被覆盖了。
自然可以通过额外临时空间解决。但这样每次要使用 n/2 的空间。加起来空间复杂度翻倍。
如何对其进行原地合并呢？交换吗？
// 6 > 3
arr = [...2,5,3,1,2,6...]
^ ^ ^ ^
l1 m l2 r
不行，简单交换 会打乱顺序
移动吗？
// 6 > 3
arr = [...2,5,1,2,3,6...]
^ ^ ^ ^
l1 m l2 r
也不是不行，但是这样导致每次操作移动一串数据，效率低下（$O(n^2)$ ）。（这种方法称为死板归并排序）
经过一些资料的搜索，我发现这个问题并不简单。
高德纳的《计算机程序设计艺术》第三卷将这个问题作为习题提出。而刘新宇《算法新解》第 13 中解释了这个方法。
原地工作区排序原理
简而言之，就是利用未排序的部分作为工作区（即排序的临时操作区域）。数据宏观上呈现这样的变化：
+------------------------------------------+
| 未排序 1/1 |
+------------------------------------------+
+---------------------+--------------------+
| 未排序 1/2 | 已排序 1/2 |
+---------------------+--------------------+
+----------+----------+--------------------+
| 已排序1/4 | 工作区 | 已排序1/2 |
+----------+----------+--------------------+
+----------+-------------------------------+
| 工作区 | 已归并3/4 |
+----------+-------------------------------+
每轮操作，未排序的部分数量呈指数衰减。时间复杂度是 $O(n)$。
它是如何避免覆盖问题呢？
总是对未排序部分的后⼆分之⼀排序，从⽽将已序结果交换到前⼀半，⽽使得新的⼯作区位于中间。这样就不断将⼯作区的⼤⼩减半，从 1/2 到 1/4 到 1/8……归并的规模不断下降。当⼯作区中只剩下⼀个元素时，我们⽆须继续排序，因为只含有⼀个元素的数组⾃然是已序的。归并只含有⼀个元素的数组等价于插⼊元素。实际上，我们可以使⽤插⼊排序来处理最后的⼏个元素
**注意下面是如何选取工作区的**
9 6 5 2 2 1 6
排序后半
--- 子问题：2 1 6 的排序
------- 排序后半
---------- 子问题：6 的排序，单个元素无需操作
------- 2 1 [6] // 方括号表示已排序的部分
------- 将 1 作为工作区，对 2 排序
---------- 子问题：2 的排序，单个元素无需操作
---------- [2] 1 [6]
---------- 将 [2] 归并到 [6]：交换 2 <-> 1
---------- 1 [2 6]
----------工作区只剩一个元素，交换法原地插入排序
------ [1 2 6] 子问题解决
9 6 5 2 [1 2 6]
--- 从 9 6 5 2 中选取工作区。由于长度为 4，4/2 = 2，因此选择 5, 2 作为工作区
--- 对 9 6 排序
------- 子问题：9 6 的排序。排序后半 6，无需操作。
-------- 工作区 9，交换法原地插入排序，得到 [6 9]
--- [6 9]
[6 9] 5 2 [1 2 6]
--- 将 5 2 作为工作区，归并排序 [6 9] 和 [1 2 6] **下面是归并的核心实现**
void wmerge(Key* xs, int i, int m, int j, int n, int w) {
while (i < m && j < n)
swap(xs, w++, xs[i] < xs[j] ? i++ : j++);
while (i < m)
swap(xs, w++, i++);
while (j < n)
swap(xs, w++, j++);
}
下面是以此代码为原理的例子：
------ 两个分组的索引是 [i, m) ; [j,n); w 是工作区起始索引
------ [6 9] 5 2 [1 2 6]
------- ^i mw ^j n
------- 6 >= 1，交换 w 与 j (5<->1), j++,w++
------ [6 9] 1 2 [5 2 6]
------- ^i w ^j
------- 6 >= 2，交换 w 与 j (2<->2), j++,w++
------ [6 9] 1 2 [5 2 6]
------- ^i w ^j
------- 6 >= 6，交换 w 与 j (5<->6), j++, w++
------ [6 9] 1 2 [6 2 5]
------- ^i w ^j
------- 此时 j 已经出界。i 中剩余与工作区交换.
------- 交换 2, 6
------ [6 9] 1 2 [6 2 5]
------- ^i w^j
------- 交换 5, 9
------ [2 9] 1 2 [6 6 5]
------- ^i w^j
------ [2 5] 1 2 [6 6 9]
------- ^i w^j
----此时从 [已排序][工作区][已排序]，变成了 [工作区][已归并]
--- 2 5 [1 2 6 6 9]
--- 选取 5 作为工作区：
--- [2] 5 [1 2 6 6 9]
--- 重复上面的 merge 操作：
--- [2] 5 [1 2 6 6 9]
--- 2 >= 1
--- swap 5,1
--- [2] 1 [5 2 6 6 9]
--- 2 >= 2
--- swap 5,2
--- [2] 1 [2 5 6 6 9]
--- 2 < 6
--- swap 5,2
--- [5] 1 [2 2 6 6 9]
--- swap 6,6
--- [5] 1 [2 2 6 6 9]
--- swap 6,6
--- [5] 1 [2 2 6 6 9]
--- swap 9,9
--- [5] 1 [2 2 6 6 9]
--- 即得到：
--- 5 [1 2 2 6 6 9]
工作区 5，只剩一个在工作区，简单插入即可：
--- [1 2 2 5 6 6 9]
读者可以自行测试，merge 参考代码：
1template <typename T> void print_vec(std::vector<T> &vec) {
2 if (vec.size() == 0) {
3 printf("{}\n");
4 return;
5 }
6 printf("{");
7 for (size_t i = 0; i < vec.size() - 1; i++) {
8 cout << vec[i] << ", ";
9 }
10 cout << vec[vec.size() - 1];
11 printf("}\n");
12}
13
14void swap(vector<int> &xs, int i, int j) {
15 printf("swap %d,%d\n", xs[i], xs[j]);
16 int tmp = xs[i];
17 xs[i] = xs[j];
18 xs[j] = tmp;
19}
20
21void wmerge(vector<int> &xs, int i, int m, int j, int n, int w) {
22 while (i < m && j < n) {
23 if (xs[i] < xs[j]) {
24 printf("%d < %d \n", xs[i], xs[j]);
25 } else {
26 printf("%d >= %d \n", xs[i], xs[j]);
27 }
28 swap(xs, w++, xs[i] < xs[j] ? i++ : j++);
29 print_vec(xs);
30 }
31 while (i < m) {
32 swap(xs, w++, i++);
33 print_vec(xs);
34 }
35 while (j < n) {
36 swap(xs, w++, j++);
37 print_vec(xs);
38 }
39}
这样，我们完成了归并排序。
时间复杂度：$O(n \log_{} n) $ （网上传的 $O(n^2)$ 复杂度原地归并，是因为使用了移动数组，而我们通过原地开辟工作区+交换，将其优化掉了！ ）
空间复杂度：$O(1)$（网上传的 $O(N)$ 复杂度，是因为 merge 开辟了临时数组，我们已经将其优化掉！）
有兴趣的可以搜索论文：Jyrki Katajainen, Tomi Pasanen, Jukka Teuhola - Practical in-place mergesort