递归分治算法之合并排序（Java版本）

/**
 * 排序算法学习之合并排序
 * @author Sking
 
 实现方法：
将待排序数组中相邻元素两两配对作为子数组，排序各个子数组，
 构成n/2组长度为2的排序好的子数组；然后将长度为2的子排序
 子数组再两两配对，并排序，构成长度为4的已排序子数组。如此递归
 直到整个数组是已排序为止。
 
  最坏时间复杂度：O(n*log(n))
  平均时间复杂度：O(n*log(n))
  辅助空间：O(n)
  稳定性：稳定
 */
package 递归分治;

public class MergeSort {
	@SuppressWarnings("rawtypes")
	/**
	 * 对输入数组执行合并排序
	 * @param a 指定数组，索引有效位置从0开始
	 */
	public void mergeSort(Comparable[] a) {
		Comparable[] b = new Comparable[a.length];// 辅助空间
		int s = 1;// 初始子数组长度设置为1
		while (s < a.length) {
			mergePass(a, b, s);
			s += s;
			mergePass(b, a, s);
			s += s;
		}
	}

	/**
	 * 合并相邻的已排序子数组为更大的已排序子数组
	 * 
	 * @param x
	 *            包含了已排序子数组的数组
	 * @param y
	 *            包含更大的已排序子数组的数组
	 * @param s
	 *            已排序子数组的长度
	 */
	@SuppressWarnings("rawtypes")
	public static void mergePass(Comparable[] x, Comparable[] y, int s) {
		int i = 0;
		while (i <= x.length - 2 * s) {// 合并两相邻的长度为s的已排序子数组
			merge(x, y, i, i + s - 1, i + 2 * s - 1);
			i = i + 2 * s;
		}// 当i>x.length-2*s的时候退出while循环
			// 处理剩下的部分，可以是s长度的已排序数组+“零片”
			// 也可能只是“零片“，此时不需要合并。
		if (i + s < x.length) {
			// 合并相邻的长度s的已排序子数组和长度小于s的“零片”
			merge(x, y, i, i + s - 1, x.length - 1);
		} else
			// 处理”零片“
			for (int j = i; j < x.length; j++)
				y[j] = x[j];
	}

	/**
	 * 合并已排序子数组c[l...m]和c[m+1,r]到新数组中，新数组保持有序
	 * 
	 * @param c存放两个已排序数组的数组
	 * @param d
	 *            新数组，用于存放合并后的数组
	 * @param l
	 *            左边子数组的起始索引
	 * @param m
	 *            左边子数组的结束索引
	 * @param r
	 *            右边子数组的结束索引
	 */
	@SuppressWarnings({ "unchecked", "rawtypes" })
	static void merge(Comparable[] c, Comparable[] d, int l, int m, int r) {
		int i = l;// 第一个子数组的索引指针
		int j = m + 1;// 第二个子数组的索引指针
		int k = l;// 新数组的索引指针
		while ((i <= m) && (j <= r))
			if (c[i].compareTo(c[j]) <= 0)
				d[k++] = c[i++];
			else
				d[k++] = c[j++];
		if (i > m)// 将右边子数组剩下的元素添加到新数组中
			for (int q = j; q <= r; q++)
				d[k++] = c[q];
		else
			// 将左边子数组剩下的元素添加到新数组中
			for (int q = i; q <= m; q++)
				d[k++] = c[q];
	}

	public static void main(String[] args) {
	}
}