排序之归并排序

    public void mergeSort(int[] arr){
		mSort(arr,0,arr.length-1);
	}

	/**
	 * 先拆分，再归并
	 * @param arr
	 * @param min
	 * @param max
	 */
	private void mSort(int[] arr, int min, int max) {
		int mid = (min + max) / 2;
		if(min < max){
			mSort(arr,min,mid);			// 拆分arr[min...mid]
			mSort(arr,mid+1,max);		// 拆分arr[mid+1...max]
			merge(arr,min,mid,max);		// 归并有序序列arr[min...mid]和有序序列arr[mid+1...max]
		}
	}

	/**
	 * 归并arr[min...mid]和arr[mid+1...max]
	 * 此时arr[min...mid] arr[mid+1...max]分别有序
	 * @param arr
	 * @param min
	 * @param mid
	 * @param max
	 */
	private void merge(int[] arr, int min, int mid, int max) {
		int[] tarr = new int[max+1];
		int i=min,j=mid+1,tIndex=min;
		// 将arr[min...mid]与arr[mid+1...max]中元素从小到大逐个赋值到tarr数组中
		while(i<=mid && j<=max){
			if(arr[i] < arr[j]){
				tarr[tIndex++] = arr[i++];
			} else {
				tarr[tIndex++] = arr[j++];
			}
		}
		// arr[min...mid]中元素已经全部赋值到tarr中，将arr[mid+1...max]剩余的元素赋值到tarr中
		if(i>mid){
			while(j<=max){
				tarr[tIndex++] = arr[j++];
			}
		}
		// arr[mid+1...max]中元素已经全部赋值到tarr中，将arr[min...mid]剩余的元素赋值到tarr中
		if(j>max){
			while(i<=mid){
				tarr[tIndex++] = arr[i++];
			}
		}
		//将临时数组tarr中有序序列赋值到目标数组arr中，使之arr[min...max]有序
		for(int k=min; k<=max; k++){
			arr[k] = tarr[k];
		}
	}