归并排序

归并排序 是一种基于分治思想的排序算法。分治，即分而治之。主要原理是先把一个大问题分解为多个小问题，再分别处理，最后合并。

好处

复杂度相对会比快排快一点，也比快排好打
特别是对于不让用Sort的老师需要手打排序的情况下

步骤如下：

1. 把长度为n的数组递归分为n段 （分）
2. 两两和并，每次取两个子序列开头小的数放在一个新序列里 （治）
3. 把新序列覆盖到旧序列

The code there:

#include <bits/stdc++.h>
using namespace std;
int a[1000000],b[1000000];
void sort(int l, int r)
{
	if (l==r) return;
	int mid=(r+l)/2;
	sort(l,mid); sort(mid+1,r);
	int x=l,y=mid+1,z=l;
	while (x <= mid && y <= r)
	{
		if (a[x]>a[y]) b[z++]=a[y++];
		else b[z++]=a[x++];
	}
	while (x<=mid) b[z++]=a[x++];
	while (y<=  r) b[z++]=a[y++];
	for (int i = l ; i <= r ; ++i) a[i]=b[i];
}
int main()
{
	int n; cin >> n;
	for (int i = 0 ; i < n ; ++i) scanf("%d",&a[i]);
	sort(0,n-1);
	for (int i = 0 ; i < n ; ++i) printf("%d\n",a[i]);
	return 0;
}

注意

如果题目的输入输出的量很大，要用scanf和printf，速度明显更快。