归并排序

1.确定分界点：mid=(l+r)/2

2.递归排序left,right

3.归并合二为一

int tmp[N];//辅助数组存元素
void merge_sort(int q[],int l,int r)
{
	if(l>=r) return;
	int mid=l+r>>1;//确定中点为分界点
	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)
		if(q[i]<=q[j) tmp[k++]=q[i++];//i后移，指向下一个元素
		else tmp[k++]=q[j++];
	//如果左半段还没有遍历完
	while(i<=mid) tmp[k++]=q[i++];
	//如果右半段还没有遍历完
	while(j<=r) tmp[k++]=q[j++];
	//数组存回q
	for(int i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];
}