归并排序

• 时间复杂度 \(o(nlogn)\)
• 空间复杂度 \(o(n)\)
• 模板:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;
int a[N], b[N];

// 合并
void merge(int left, int right, int mid) {
	// 标记左右半区第一个未排序的元素
	int l_pos = left, r_pos = mid + 1;
	// 临时数组元素下标
	int pos = left;
	// 合并过程
	while(l_pos <= mid && r_pos <= right) {
		if(a[l_pos] < a[r_pos]) 	// 左半区第一个剩余元素更小
			b[pos ++] = a[l_pos ++];
		else						// 右半区第一个剩余元素更小
			b[pos ++] = a[r_pos ++];
	}
	// 合并左半区剩余元素
	while(l_pos <= mid) {
		b[pos ++] = a[l_pos ++];
	}
	// 合并右半区剩余元素
	while(r_pos <= right) {
		b[pos ++] = a[r_pos ++];
	}
	// 将临时数组复制回原来的数组
 	while(left <= right) {
		a[left] = b[left];
		left ++;
	}
}
// 归并排序
void msort(int left, int right) {
	// 如果只有一个元素， 那么就不需要继续划分
	if(left < right) {
		// 找中间点
		int mid = (left + right) / 2;
		// 递归划分左半区
		msort(left, mid);
		// 递归划分右半区
		msort(mid + 1, right);
		// 合并已经排序的部分
		merge(left, right, mid);
	}
}
int main() {
	cin >> n;
	for(int i = 0; i < n; i ++) {
		cin >> a[i];
	}
	msort(0, n - 1);
	for(int i = 0; i < n; i ++) {
		cout << a[i] << " ";
	}
    return 0;
}