归并排序

归并排序是一种十分优秀的排序算法，而且通过归并排序还可以用来求逆序对，这个我们后面再说。

归并的原理和注意点就一个例子就可以解释了：

有数列：2 7 5 4 9 8 6

利用归并排序：

先二分：

2 7 5 4 9 8 6

再分开排序：

2 4 5 7 6 8 9

取第一个数列第一个数与第二个数列第一个数进行比较，取较小的一个数加入一个临时数组，而后删除这个数：

4 5 7 6 8 9

重复以上步骤得：

​ 8 9

会发现此时第二个数组还有两数，而第一个数列已被弹空，此时就直接将第二个数列的所有剩下的加入临时数组，最后再将临时数组里的数一一赋值给原数组。

代码实现：

#include <bits/stdc++.h>

#define ll long long//将 long long 用 ll 替换 

using namespace std;

ll a[1000001], b[1000001], n;// a为原数组，b为临时数组 

void mergesort(ll l, ll r) {
	if(l >= r) return ;//停止条件 
	ll m = l + (r - l) / 2;//二分，m = l + (r - l) / 2 和 m = (l + r) / 2 是一样的，这里为防止溢出 
	mergesort(l, m);//递归左边 
	mergesort(m + 1, r);//递归右边 
	ll l1 = l;//第一个数列指针 
	ll l2 = m + 1;//第二个数列指针 
	ll lb = l;//临时数组指针 
	while(l1 <= m || l2 <= r) {
		if(l1 > m) {b[lb ++] = a[l2]; l2 ++;}//第一个数列走完时 
		else if(l2 > r) {b[lb ++] = a[l1]; l1 ++;}//第二个数列走完时 
		else {//第一个数列和第二个数列都有数时 
			if(a[l1] < a[l2]) {b[lb ++] = a[l1]; l1 ++;}//第一个数列第一个数小于第二个数列第一个数时 
			else {b[lb ++] = a[l2]; l2 ++;}//第一个数列第一个数大于第二个数列第一个数时
		}
	}
	for(int i = l; i <= r; i ++) {
		a[i] = b[i];//赋值回去 
	}
}

int main() {
	cin >> n;
	for(int i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	mergesort(1, n);
	for(int i = 1; i <= n; i ++) {
		cout << a[i] << " ";
	}
	return 0;
}