1.2归并

解释都写在代码注释里了，请配合代码一起食用。 

其实就是把原来的数列从中间砍成两部分，然后再四份、八份、十六份...直到不能分为止。然后重排两个最小单元的顺序，排好序后再把小单元合并成中等单元，重排两个中等单元的顺序，排好序好再合并成大单元，重排两个大单元的顺序...以此类推，是为归并排序。

#include<iostream>
using namespace std;
const int N=1e6+10;

int n=0;
int a[N]={0},tmp[N]={0};

void merge_sort(int q[],int l,int r){
	if(l>=r) return; //l在r后面，结束 
	int mid = l+r>>1;//(l+r)/2的意思
	merge_sort(q,l,mid);merge_sort(q,mid+1,r);//与快排不同，归并是先内嵌调用再调整顺序
	
	int k=0,i=l,j=mid+1;//i是第一部分的开头，j是第二部分的开头
	while(i<=mid && j<=r) //i、j都没走到自己那部分的结尾
		if(q[i]<=q[j]) tmp[k++]=q[i++];
		else tmp[k++]=q[j++]; //两部分的开头比较，哪个小把哪个放tmp数组里，然后指针后移
	//当两部分中的某一部分全部放入tmp后 
	while(i<=mid) tmp[k++]=q[i++];//i所在的部分有剩余则全部放到tmp末尾 
	while(j<=r) tmp[k++]=q[j++]; //j所在的部分有剩余则全部放到tmp末尾 
	
	for(i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];	 
}

int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%d",&a[i]);
	merge_sort(a,0,n-1);
	for(int i=0;i<n;i++) printf("%d ",a[i]);
	return 0;
}

与快排不同，快排是先整体调整顺序（不是最终顺序）后再分成两份、四份、八份...来逐步微调，即从整体到局部的顺序调整。而归并是先把整体分解然后再调整，再合并，是从局部到整体的调整顺序。