public class Solution {
	
	// 子环节，归并两个有序的数组
	public void MergeSort(int[] arr, int left, int mid, int right){
		int[] arr2 = new int[mid - left + 1];
		int[] arr3 = new int[right - mid];
		int length1 = mid - left + 1;
		int length2 = right - mid;
		for(int i = 0; i < length1; i++)
			arr2[i] = arr[i + left];
		for(int i = 0; i < length2; i++)
			arr3[i] = arr[i + mid + 1];
		int i = left, j = 0, k = 0;
		while(j< length1 && k < length2) {
			if(arr2[j] > arr3[k]) {
				arr[i++] = arr3[k];
				k++;
			}else {
				arr[i++] = arr2[j];
				j++;
			}
		}
		while(j < length1) {
			arr[i++] = arr2[j++];
		}
		while(k < length2) {
			arr[i++] = arr3[k++];
		}
	}
  
	// [left, right]
	// 递归的归并排序
	public void Merge(int[] arr, int left, int right){
		
		if(left < right) {	
		int mid;
		mid = (left + right) / 2;
		Merge(arr, left, mid);
		Merge(arr, mid+1, right);
		MergeSort(arr, left, mid, right);
		
		}
	}
	// 非递归的归并排序
	public void Merge2(int[] arr, int n) {
		for(int size = 1; size <= n; size += size)
			for(int i = 0; i + size - 1< n; i += 2*size)
				MergeSort(arr, i, i + size - 1, Math.min(i + 2*size - 1, n-1));
	}
    public static void main(String[] args) {
		int[] arr = new int[]{1, 3, 2, 0, 9, 5, 7, -8, -7};
		Solution solution = new Solution();
		solution.Merge(arr, 0, arr.length-1);
		//solution.Merge2(arr, arr.length);
		for(int i : arr) {
			System.out.print(i + " ");
		}
	}
}