public static void merge(int[] arr, int left, int mid, int right){
		//分成左右两个数组，左边是left,left+1,...mid
		//右边是mid+1,mid+2,...,right
		int lsize = mid - left + 1;
		int rsize = right - mid;
		int[] L = new int[lsize + 1]; //加上最后一个哨兵（最大值）
		int[] R = new int[rsize + 1];
		
		for(int i=0; i<lsize; i++){
			L[i] = arr[left + i];
		}
		L[L.length - 1] = Integer.MAX_VALUE;
		for(int j=0; j<rsize; j++){
			R[j] = arr[mid + 1 + j];
		}
		R[R.length - 1] = Integer.MAX_VALUE;
		
		int i = 0;
		int j = 0;
		for(int k = left; k<=right; k++){
			if(L[i] <= R[j]) 
				arr[k] = L[i++];			
			else
				arr[k] = R[j++];
		}	
	}