import java.util.Arrays;

/**
 * 归并排序
 * @author 123
 *
 */
public class Sort8 {
	public static void merge(int[] A,int left,int right){
		int middle = (left+right)/2;
		int[] B = new int[middle-left+1];
		int[] C = new int[right-middle];
		int i1 = 0,j1 = 0;
		//原数组前半部分赋值给B[]
		for(int i=left;i<=middle;i++){
			B[i1] = A[i];
			i1++;
		}
		//原数组后半部分赋值给C[]
		for(int j=middle+1;j<=right;j++){
			C[j1] = A[j];
			j1++;
		}
		int i2 = 0,j2 = 0,index = left;
		//排序
		while(i2<B.length&&j2<C.length){
			if(B[i2]<=C[j2]){
				A[index] = B[i2];
				i2++;
			}else{
				A[index] = C[j2];
				j2++;
			}
			index++;
		}
		//将未排完部分直接放到数组末尾
		while(i2==B.length&&j2<C.length){
			A[index]=C[j2];
			j2++;
			index++;
		}
		while(j2==C.length&&i2<B.length){
			A[index]=B[i2];
			i2++;
			index++;
		}
		System.out.println("Stage  "+Arrays.toString(A));
	}
	public static void mergeSort(int[] A,int left,int right){
		//如果一组分好数组只有1个元素,返回
		if(left==right){
			return;
		}else{
			int middle = (left+right)/2;
			mergeSort(A,left,middle);
			mergeSort(A,middle+1,right);
			merge(A,left,right);
		}
	}
}