排序－归并

归并排序的时间效率为O(n * log n)

算法假设两个已有序的数组，将其归并成一个有序的数组（见merge函数)。算法将数组分为前后两部分，对这两部分递归调用归并排序，然后将这两部分再合并。

算法的空间效率不高，需要多耗费一倍的空间。

class Merge {
	public static void main(String[] args) {
		int[] a = {3,2,5,2,0,6,3,7};
		sort(a,0,a.length);
		print(a);
	}

	public static void sort(int[] a, int p1, int p3) {
		if((p3-p1) <= 1) return; //判断是否不需要继续递归

		int p2 = (p3 + p1)/2; //计算中间位置p2

		sort(a,p1,p2); //将p1 ~ p2之间递归排序
		sort(a,p2,p3); //将p2 ~ p3之间递归排序 
		
		merge(a,p1,p2,p3); //合并p1~p2,p2~p3
	}

	public static void merge(int[] a, int p1, int p2 ,int p3) {
		int[] c = new int[p3 - p1];
		int n = p1, m = p2, i = 0;
		while(n< p2 && m<p3) {
			if(a[n] < a[m]) c[i++] = a[n++];
			else c[i++] = a[m++];
		}
		while(n < p2) c[i++] = a[n++];
		while(m < p3) c[i++] = a[m++];

		for(int j=0; j<c.length; j++) a[p1 + j] = c[j]; 
	}

	public static void print(int[] c) {
		for(int i: c) System.out.print(i + " " );
		System.out.println();
	}

}