归并算法（详细见解）

原理：使用递归方法来实现归并排序时，主要是两个“有序子序列”的合并 (1)将待排序序列从中间一分为二，对左右两边再进行递归分割操作，使用递归，得到n个相互独立的子序列（过程像二叉树那样）； (2)对n个独立的子序列递归的执行合并操作，最终得到有序的序列。

( 80，30，60，40，20，10，50，70)

（80，30，60，40） （20，10，50，70）

（80，30） （60，40） ( 20，10) (50,70)

( 80) (30) (60) (40) (20) (10) (50) (70)（第一步）

(30，80) (40，60) (10，20) (50，70)

(30，40，60，80) (10，20，50，70)

(10，20，30，40，50，60，70，80) （第二步）

最后归并的时候方法

#include<stdio.h>
#include<stdlib.h>
void fun(int a[],int l,int avg,int rend){
	int *tmp=(int *)malloc(sizeof(int));//开辟空间 
	int i=l;//l是左边数组下标 
	int j=avg+1;//avg是中间的数加1是右边数组下标 
	int k=0;
	while(i<=avg&&j<=rend){ //左右两边进行比较把小的存放到tmp数组 
		if(a[i]<=a[j])
			tmp[k++]=a[i++];
		else
			tmp[k++]=a[j++];
	}//左右两边进行比较把较小的数赋值给tmp数组里面 
	while(i<=avg)//把左边剩余的数组元素传入tmp数组 
		tmp[k++]=a[i++];
	while(j<=rend)//把右边剩余的数组元素传入tmp数组 
		tmp[k++]=a[j++];
	for(i=0;i<k;i++)//把新数组中的数覆盖到a数组中 
		a[l+i]=tmp[i];	
	}
void fun1(int a[],int l,int rend){
	if(a==NULL||l>=rend)
		return;
	int avg=(l+rend)/2;
	fun1(a,l,avg);//左边数组排序 
	fun1(a,avg+1,rend);//右边数组排序 
	fun(a,l,avg,rend);//合并左右数组 
}
int lenght(int a[]){//读取数组长度 
	int count;
	while(a[count]!=){
		count++;
	}
		return count;
}
int main(){
	int i;
	int a[]={80,30,60,40,20,10,50,70};
	int ilen=lenght(a);
	printf("before sort:");
	for(i=0;i<ilen;i++)
		printf("%d  ",a[i]);
	printf("
");
	
	fun1(a,0,ilen-1);
	printf("after sort：");
	for(i=0;i<ilen;i++)
		printf("%d  ",a[i]);
	printf("
");
	return 0;
}

fun1递归的得到是n个子序列

fun在对有序子序列进行归并

输入进行归并算法，将主函数调换即可

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