[数据结构与算法]洛谷1177-归并排序--C++（归并排序）

归并排序的步骤就是先划分，再把两部分进行两两合并，合并的时候就用到了归并排序。归并排序是一个稳定的排序，算法的时间效率是O(nlgn)，空间效率是O(n)，是一个比较好的排序。
AC代码

#include<iostream>
using namespace std;
const int N=100010;
int a[N];
int n;
void merge(int l,int r,int mid){
	int tmp[N]={0};
	int lpos=l,rpos=mid+1,pos=l;
	while(lpos<=mid && rpos<=r){
		if(a[lpos]<=a[rpos]){
			tmp[pos++]=a[lpos++];
		}
		else{
			tmp[pos++]=a[rpos++];
		}
	}
	while(lpos<=mid){
		tmp[pos++]=a[lpos++];
	}
	while(rpos<=r){
		tmp[pos++]=a[rpos++];
	}
	for(int i=l;i<=r;i++)
		a[i]=tmp[i];
}
void merge_sort(int l,int r){
	if(l<r){
		int mid=l+(r-l)/2;
		merge_sort(l,mid);
		merge_sort(mid+1,r);
		merge(l,r,mid);
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	merge_sort(1,n);
	for(int i=1;i<=n;i++)
		printf("%d ",a[i]);
	return 0;
}