归并排序

public class MergeSort {

	public static int[] Sort(int[] a) {
		/* 此处使用和原数组大小一样的数组 */
		int[] b = new int[a.length];/*额外的数组空间*/
		mergeSort(a, b, 0, a.length - 1);
		return a;
	}

	private static void mergeSort(int[] a, int[] b, int low, int high) {
		if (low < high) {
			int mid = (low + high) / 2;
			/*不断进行递归分解，直到合并的长度为1时找到递归出口，开始沿递归路径向上走*/
			mergeSort(a, b, low, mid);
			mergeSort(a, b, mid + 1, high);
			merge(a, b, low, mid, high);
		}
	}
	
	private static void merge(int[] a, int[] b, final int left, final int center,
			final int right) {
		
		int bPos = left;/*临时数组的索引*/
		
		/*使用以下临时变量主要用于便于理解，不易产生混淆*/
		int leftStart = left;/*左起始点*/
		int leftEnd = center;/*左结束点*/
		int rightStart = center + 1;/*右起始点*/
		int rightEnd = right;/*右结束点*/

		/*在两个左右分解数组中选出最小的一个放入临时数组中*/
		while (leftStart <= leftEnd && rightStart <= rightEnd) {
			if (a[leftStart] <= a[rightStart])
				b[bPos++] = a[leftStart++];
			else {
				b[bPos++] = a[rightStart++];

			}
		}
		
		/*如果有剩余直接复制到临时数组里*/
		while (leftStart <= leftEnd) {
			b[bPos++] = a[leftStart++];
		}
		while (rightStart <= rightEnd) {
			b[bPos++] = a[rightStart++];
		}
		
		/*将临时数组中排好序的部分复制到原数组中*/
		for (int i = left; i <= right; i++) {
			a[i] = b[i];
		}
	}
}