归并排序（最典型的分而治之思想）

#include
#include
#include
using namespace std;

int n;

int a[100010];
int temp[100010]; //临时数组 归并的时候用

void merge(int low,int mid,int high)//二路归并 就是合并两个有序数组
{
	int k = low-1;
	int l = low, r = mid + 1; //l为左边有序数组指针，r为右边有序数组指针，k为临时数组指针（临时存放排好序的数组）
	while (l<=mid&&r<=high)//当二者指针都没有超过各自的上界时
	{
		if (a[l] <= a[r]) //谁小些就存谁，与此同时，指针移动
			temp[++k] = a[l++]; 
		else
			temp[++k] = a[r++];
	}
	while (l <= mid)  //如最后还剩左边的（右边先放完） 直接挨个儿吧有左边的放进去
		temp[++k] = a[l++];
	while (r <= high)
		temp[++k] = a[r++];		
	for (int i = low; i <= high; i++) //copy进入原数组
		a[i] = temp[i];
	return;
}
void mergesort(int low,int high)
{
	if (low >= high) return;
	int mid = low + high >> 1;  //划分
	mergesort(low, mid);   //划分左边
	mergesort(mid + 1, high);// 划分右边
	merge(low, mid, high);  //归并起来 最典型的一个分治思想的的一个东西  一个完整的递归二叉树 一直递归到左边的左子树
	                        // 然后 慢慢合并 其实就相当于一个先序遍历的问题 只是现在的遍历操作 变成了这个归并merge操作 而不是printf；
}

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<