package sort;

public class MergeSort {
	private static void merge(int[] a, int[] tmp, int l, int m, int r){
		int ll = l;
		int rr = m + 1;
		int cc = l;
		while((ll <= m) && (rr <= r)){
			if(a[ll] < a[rr]){
				tmp[cc++] = a[ll++]; 
			}else{
				tmp[cc++] = a[rr++];
			}
		}
		while(ll<=m) tmp[cc++] = a[ll++];
		while(rr<=r) tmp[cc++] = a[rr++];
		for(int i=l; i<=r; i++){
			a[i] = tmp[i];
		}
	}
	private static void mergeSort(int[] a, int[] tmp, int l, int r){
		if(l<r){
			int m = (l + (r - l) / 2);
			mergeSort(a, tmp, l,   m);
			mergeSort(a, tmp, m+1, r);
			merge(a, tmp, l, m, r);
		}
	}
	public static void Sort(int[] a){
		int[] tmp = new int[a.length];
		//归并a 存放缓存tmpArray 从0到a.length-1
		mergeSort(a, tmp, 0, a.length-1);
	}
	public static void main(String[] args) {
		int[] a = new int[]{2,3,4,8,6,7,2};
		Sort(a);
		for(int i:a){
			System.out.print(i+" ");
		}
		System.out.println();
		
	}

}