该算法使用递归法实现，思路为：每次递归将待排序数组在中间位置分成左右两组，分别对左右两个数组进行归并排序，递归的条件是数组长度必须大于等于3，所以当数组中只有两个数据的时候可以直接进行比较排序，若数组只有一个元素则无需操作。每次递归结束时，左右两个数组都是有序的，然后对这两个中的数据进行排序，使整个数组有序。直到算法结束。

public class Test8{
	
	public static int a[]=new int[]{13,12,11,10,9,8,7,46,5,4,3,2,1,58,56,45,12};
	
	public static void main(String args[]){
		rec(0,a.length-1);
		for(int i=0;i<a.length;i++){
			System.out.print(a[i]+" ");
		}
	}
	
	public static void rec(int left,int right){
		if(left+1==right){
			if(a[left]>a[right]){
                int t=a[left];a[left]=a[right];a[right]=t;
            }
		}else if(left+1<right){
			//递归条件
			int p=left+((right-left)/2);
			rec(left,p);
			rec(p+1,right);
			sort(left,p,right);
		}
	}
	
	public static void sort(int left,int p,int right){
		int[] t=new int[right-left+1];
		int i=left,j=p+1,index=0;
		while(i<=p&&j<=right){
			if(a[i]>a[j]){
				t[index++]=a[j++];
			}else{
				t[index++]=a[i++];
			}
		}
		while(i<=p){
			t[index++]=a[i++];
		}
		while(j<=right){
			t[index++]=a[j++];
		}
		for(int d=0;d<t.length;d++){
			a[left+d]=t[d];
		}
	}
}

时间复杂度：O( nlogn )

空间复杂度：由于是递归实现，所以空间复杂度为：O(n)