归并排序

归并排序由冯诺伊曼提出

1.将给定的包含n个元素的局部数组“分割”成两个局部数组，每个数组各包含n/2个元素

2.对两个局部数组分别执行mergesort排序

3.通过merge将两个已排序完毕的局部数组“整合”成一个数组。

向下的箭头代表分割，向上的箭头代表整合，箭头边的数字代表处理顺序。

当局部数组只剩下一个元素时，mergesort不做任何处理直接结束。如果不是，则计算局部数组的*位置mid，将left到mid（不包含mid）视作前半部分，mid到right（不包含right）视作后半部分，再分别套用mergesort

为了简化merge的实现，我们可以在l和r的末尾分别安插一个大于所有元素的标记。在比较l,r元素的过程中，必然会有遇到元素与标记相比较的情况，只要我们标记设置的足够大，且将比较次数限制在n1+n2（right-left)之内，就可以既防止两个标记相比较，又防止循环变量i，j分别超过n1,n2。

复杂度分析：一般来说，n个数据大致分为log2n层，由于每层执行merge的总复杂度为O（n），因此归并排序总的时间复杂度为O(nlogn)。

属于稳定排序。

缺点：还需要临时占用一部分空间。

#include<bits/stdc++.h>

using namespace std;

const int maxn=5e5+5;
const int sentinel=2e9+5;

int l[maxn/2+5],r[maxn/2+5];
//整合
void merge(int a[],int n,int left,int mid,int right)
{
	int n1=mid-left;
	int n2=right-mid;
	for(int i=0;i<n1;i++){
		l[i]=a[left+i];
	}
	for(int i=0;i<n2;i++){
		r[i]=a[mid+i];
	}
	l[n1]=r[n2]=sentinel;//很重要，设置标记，这儿非常重要
	int i=0,j=0;
	for(int k=left;k<right;k++){
		if(l[i]<=r[j]){
			a[k]=l[i++];
		}else{
			a[k]=r[j++];
		}
	}
}
//分割
void mergesort(int a[],int n,int left,int right)
{
	if(left+1<right){
		int mid=(left+right)>>1;
		mergesort(a,n,left,mid);
		mergesort(a,n,mid,right);
		merge(a,n,left,mid,right);
	}
}

int main()
{
	int a[maxn],n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	mergesort(a,n,0,n);
	for(int i=0;i<n;i++){
		if(i){
			cout<<" ";
		}
		cout<<a[i];
	}
	cout<<endl;
	return 0;
}
/*
10 
8 5 9 2 6 3 7 1 10 4
*/

归并排序除了可以对数组进行排序，还可以高效的求出数组小和（即单调和）以及数组中的逆序对。