1.算法思想：
合并排序是采用分治策略实现对N个元素进行排序的算法，是分治法的一个典型应用和完美体现，它是一种平衡，简单的二分分治策略，计算过程分为三步：
（1）分解：将待排序元素分成大小大致相同的两个子序列。
（2）求解子问题：用合并排序法分别对两个子序列递归地进行排序。
（3）合并：将排好序的有序子序列进行合并，得到符合要求的有序序列。
例如：设待排序序列A=<8,3,2,9,7,1,5,4>,采用合并排序算法对序列A进行排序。

#include<stdio.h>
#include<math.h>
#define maxx 105
int a[maxx];
int merge[maxx];
//合并两个有序子序列
void Merge(int merge[],int a[],int left,int right,int middle){
	int i=left,j=middle+1;
	int k=left;
	while(i<=middle&&j<=right){
		if(a[i]<=a[j]){
			merge[k++]=a[i++];
		}else{
			merge[k++]=a[j++];
		}
	}
	while(i<=middle)merge[k++]=a[i++];
	while(j<=right)merge[k++]=a[j++];
	i=0;
	for(i=left;i<=right;i++)a[i]=merge[i];
}
//合并排序算法
void Mergesort(int a[],int left,int right){
	if(left<right){
		int middle=(left+right)>>1;
		Mergesort(a,left,middle);
		Mergesort(a,middle+1,right);
		Merge(merge,a,left,right,middle);
    }
}
int main(){
	int n;
	while(scanf("%d",&n)!=EOF){
		int i;
		for(i=0;i<n;i++){
			scanf("%d",&a[i]);
		}
		Mergesort(a,0,n-1);
		i=0;
		for(i=0;i<n;i++){
			printf("%d ",a[i]);
		}
	}
	return 0;
}

/*
input
10
10 9 8 7 6 5 4 3 2 1

ouput
1 2 3 4 5 6 7 8 9 10
*/