先看归并排序，归并排序就是先排左，再排右，然后把这两部分merge在一起，时间复杂度是O(nlogn)的。
额外空间复杂度O(n)；
1）左部分排好序、右部分排好序、利用merge过程让左右整体有序
2）merge过程：谁小拷贝谁，直到左右两部分所有的数字耗尽，拷贝回原数组
void merge(int l, int m, int r)
{int ai = l, bi = m + 1;int i = l;while (ai <= m && bi <= r){help[i++] = a[ai] <= a[bi] ? a[ai++] : a[bi++];}while (ai <= m){help[i++] = a[ai++];}while (bi <= r){help[i++] = a[bi++];}for (int i = l; i <= r; i++){a[i] = help[i];}
}
void wo(int l, int r)
{if (l >= r)return;int mid = l + ((r - l) >> 1);wo(l, mid);wo(mid + 1, r);merge(l, mid, r);
}
void solve()
{cin >> n;a.resize(n + 1);help.resize(n + 1);for (int i = 1; i <= n; i++){cin >> a[i];}wo(1, n);for (int i = 1; i <= n; i++){cout << a[i] << ' ';}
}
也有非递归的版本
void merge(int l, int m, int r)
{int ai = l, bi = m + 1;int i = l;while (ai <= m && bi <= r){help[i++] = a[ai] <= a[bi] ? a[ai++] : a[bi++];}while (ai <= m){help[i++] = a[ai++];}while (bi <= r){help[i++] = a[bi++];}for (int i = l; i <= r; i++){a[i] = help[i];}
}
void solve()
{cin >> n;a.resize(n + 1);help.resize(n + 1);for (int i = 1; i <= n; i++){cin >> a[i];}for (int step = 1; step <= n; step *= 2){l = 0;while (l <= n){m = l + step - 1;if (m + 1 > n){break;}r = min(n, l + (step << 1) - 1);merge(l, m, r);l = r + 1;}}for (int i = 1; i <= n; i++){cout << a[i] << ' ';}
}
这里使用了归并分治的思想。
归并分治
原理：
1）思考一个问题在大范围上的答案，是否等于，左部分的答案 + 右部分的答案 + 跨越左右产生的答案
2）计算“跨越左右产生的答案”时，如果加上左、右各自有序这个设定，会不会获得计算的便利性
3）如果以上两点都成立，那么该问题很可能被归并分治解决（话不说满，因为总有很毒的出题人）
4）求解答案的过程中只需要加入归并排序的过程即可，因为要让左、右各自有序，来获得计算的便利性
举两个例子
https://www.nowcoder.com/practice/edfe05a1d45c4ea89101d936cac32469
这里的小和就可以两部分分别计算，然后合并的时候再用双指针跑一遍，发现双指针只需要遍历一遍，所以完全可以用归并分治。
```cpp
void merge(int l, int m, int r)
{int ai = l, bi = m + 1;int sum = 0;for (int i = bi; i <= r; i++){while (ai <= m){if (a[ai] <= a[i]){sum += a[ai];ai++;}else{break;}}ans += sum;}ai = l, bi = m + 1;int i = l;while (ai <= m && bi <= r){help[i++] = a[ai] <= a[bi] ? a[ai++] : a[bi++];}while (ai <= m){help[i++] = a[ai++];}while (bi <= r){help[i++] = a[bi++];}for (int i = l; i <= r; i++){a[i] = help[i];}
}
void wo(int l, int r)
{if (l >= r)return;int mid = l + ((r - l) >> 1);wo(l, mid);wo(mid + 1, r);merge(l, mid, r);
}
void solve()
{cin >> n;a.resize(n + 1);help.resize(n + 1);for (int i = 1; i <= n; i++){cin >> a[i];}wo(1,n);cout << ans << endl;
}
再举一个例子，
https://www.luogu.com.cn/problem/P1908
著名的逆序对，差不多的套路，以前我是用树状数组做，现在用这个，hhh其实都是差不多的思想
双指针跑一遍，判断左指针是否大于右指针就行了
void merge(int l, int m, int r)
{int ai = l, bi = m + 1;int sum = 0;for (int i = ai; i <= m; i++){while (bi <= r){if (a[i] > a[bi]){sum++;bi++;}else{break;}}ans += sum;}ai = l, bi = m + 1;int i = l;while (ai <= m && bi <= r){help[i++] = a[ai] <= a[bi] ? a[ai++] : a[bi++];}while (ai <= m){help[i++] = a[ai++];}while (bi <= r){help[i++] = a[bi++];}for (int i = l; i <= r; i++){a[i] = help[i];}
}
void wo(int l, int r)
{if (l >= r)return;int mid = l + ((r - l) >> 1);wo(l, mid);wo(mid + 1, r);merge(l, mid, r);
}
void solve()
{cin >> n;a.resize(n + 1);help.resize(n + 1);for (int i = 1; i <= n; i++){cin >> a[i];}wo(1, n);cout << ans << endl;
}