合并排序

合并排序属于稳定排序的一种，也是一种外部排序。一般用户文件排序，空间复杂度为O(n)

package algorithms;

/**
 * 合并排序
 * @author heng
 * @date 2010-6-26
 */
public class MergeSort {

	public static void main(String[] args) {
		int[] x = { 10, 2, 33, 44, 0, 55, 1, 8, 7, 6, 20, 19, 35 };
		MergeSort ms = new MergeSort();

		System.out.println("原数组：");
		for (int x1 : x) {
			System.out.print(x1 + " ");
		}
		System.out.println();
		System.out.println("=====================================================");

		ms.mergeSort(x, 1, x.length);
	}

	/**
	 * 排序数据划分
	 * @param a
	 * @param start
	 * @param end
	 */
	public void mergeSort(int[] a, int start, int end) {

		if (start < end) {
			int mid = (start + end) / 2;//计算合并的字数组边界

			
			//递归操作
			mergeSort(a, start, mid);
			mergeSort(a, mid + 1, end);
			
			//合并各字数组
			merge(a, start, mid, end);

		}
	}

	/**
	 * 合并排序方法
	 * 
	 * 排序后是以小到大的从左往右的顺序
	 * 
	 * @param a
	 * @param start
	 * @param mid
	 * @param end
	 */
	public void merge(int[] a, int start, int mid, int end) {
		int l1 = mid - start + 1;
		int l2 = end - mid;

		int[] L = new int[l1];
		int[] R = new int[l2];

		for (int i = 0; i < L.length; i++) {
			L[i] = a[start + i - 1];
		}

		for (int i = 0; i < R.length; i++) {
			R[i] = a[mid + i];
		}

		int z = 0;
		int j = 0;
		int k = 0;
		for (k = start - 1; k < end - 1; k++) {
			if (L[z] < R[j]) {
				a[k] = L[z];
				z++;
			} else {
				a[k] = R[j];
				j++;
			}

			if (z >= l1) {
				break;
			} else if (j >= l2) {
				for (int t = z; t < l1; t++) {//把没有处理的数据依序加入数组中
					a[++k] = L[t];
				}
				break;
			}
		}

		for (int x : a) {//每次排序的结果
			System.out.print(x + " ");
		}
		System.out.println();
	}
}