参考代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, a[N], tmp[N];
void merge_sort(int l, int r) {
if (l >= r) return;
int mid = l + r >> 1;
merge_sort(l, mid), merge_sort(mid + 1, r);
inplace_merge(a + l, a + mid + 1, a + r + 1);
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
merge_sort(1, n);
for (int i = 1; i <= n; i++) cout << a[i] << ' ';
}
inplace_merge(a + 1, a + mid + 1, a + n + 1);
轻松解决$[l,mid],[mid+1,r]$的合并!
介绍用法:
-
inplace_merge(bg,md,ed)
-
将 $[bg,md)$ 和 $[md,ed)$ 归并,并存入 bg。(注意开闭区间)
-
时间复杂度 $O(n)$,需要 $O(n)$ 的额外空间。
-
当空间不足时使用 $O(n \log n)$ 的原地排序。
-
常数较小,可能比手写的还快。
-
可以传入第四个参数作为比较函数。
-
常用于 CDQ 分治等分治算法,非常好用。
非常好用!!