归并排序

1. 整体就是一个简单的递归，左边排好序、右边排好序、让其整体有序
2. 让其整体有序的过程里用了外排序方法
3. 利用master公式来求解时间复杂度
4. 归并排序的实质

时间复杂度O(N*logN)，额外空间复杂度O(N)

public class Mergesort {
	
	public static void mergeSort(int[] arr) {
		if(arr == null || arr.length < 2) {
			return;
		}
		process(arr, 0, arr.length - 1);
	}
	
	public static void process(int[] arr, int L, int R) {
		if(L == R) {
			return;
		}
		//mid = (R+L)/2 --> mid = L+(R-L)/2 除2相当于向右移一位
		int mid = L + ((R - L) >> 1);
		process(arr, L, mid);
		process(arr, mid + 1, R);
		merge(arr, L, mid, R);
	}
	
	public static void merge(int[] arr, int L, int M, int R) {
		int[] help = new int[R - L + 1];
		int i = 0;
		int p1 = L;
		int p2 = M + 1;
		while(p1 <= M && p2 <= R) {
			help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
		}
		while(p1 <= M) {
			help[i++] = arr[p1++];
		}
		while(p2 <= R) {
			help[i++] = arr[p2++];
		}
		for(i = 0; i < help.length; i++) {
			arr[L + i] = help[i];
		}
	}

}