#include <stdio.h>
//待排序數組
int A[10]={2,6,3,8,7,4,9,0,1,5};
//歸并兩個子集合
void merge(int low,int mid,int high){
	//輔助數組，存放中間結果
	int B[10];
	int i,j,k,l;
	i=low;
	j=low;
	k=mid+1;
	while(i<=mid && k<=high){
		if(A[i]<A[k]){
			B[j]=A[i];
			i++;
		}
		else{
			B[j]=A[k];
			k++;
		}
		j++;
	}
	if(i>mid){
		for(l=k;l<=high;l++){
			B[j]=A[l];
			j++;
		}
	}
	else{
		for(l=i;l<=mid;l++){
			B[j]=A[l];
			j++;
		}
	}
	//把已排序數組復制到待排序數組
	for(i=low;i<=high;i++){
		A[i]=B[i];
	}
}
//歸并分類
void mergesort(int low,int high){
	int mid;
	if(low<high){
		mid=(low+high)/2;
		//分類
		mergesort(low,mid);
		mergesort(mid+1,high);
		//歸并兩個已經分類的子集合
		merge(low,mid,high);
	}
}
void main(){
	//打印原始數據
	int i;
	printf("原始待排序數據：");
	for(i=0;i<=9;i++){
		printf("%-4d",A[i]);
	}
 	mergesort(0,9);
	//輸出結果到屏幕
	printf("\n歸并排序之后：");
	for(i=0;i<=9;i++){
		printf("%-4d",A[i]);
	}
	printf("\n");
}