归并排序

public class MergeSort {
	public static void print(int[] c) {
		for (int i = 0; i < c.length; i++) {
			System.out.print(c[i] + " ");
		}
		System.out.println();
	}

	public static void merge(int[] a, int[] b, int[] c) {
		int i, j, k;
		for (i = 0, j = 0, k = 0; i < a.length && j < b.length; k++) {
			if (a[i] <= b[j]) {
				c[k] = a[i++];
			} else {
				c[k] = b[j++];
			}
		}
		while (i < a.length) {
			c[k++] = a[i++];
		}
		while (j < b.length) {
			c[k++] = b[j++];
		}
	}

	public static void merge(int[] array, int lFirst, int lEnd, int rFirst,
			int rEnd) {
		int temp[] = new int[lEnd - lFirst + rEnd - rFirst + 2];
		int i = lFirst, j = rFirst, k = 0;
		for (; i <= lEnd && j <= rEnd;) {
			if (array[i] <= array[j]) {
				temp[k++] = array[i++];
			} else {
				temp[k++] = array[j++];
			}
		}
		while (i <= lEnd) {
			temp[k] = array[i++];
			if (k == temp.length - 1)
				break;
			k++;
		}
		while (j <= rEnd) {
			temp[k] = array[j++];
			if (k == temp.length - 1)
				break;
			k++;
		}
		for (int m = lFirst, n = 0; m <= rEnd; m++, n++) {
			array[m] = temp[n];
		}
		temp = null;
	}

	private static void processMergeSort(int[] array, int first, int last) {
		if (first < last) {
			int mid = (first + last + 1) / 2;
			// 左序列
			processMergeSort(array, first, mid - 1);
			// 右序列
			processMergeSort(array, mid, last);
			merge(array, first, mid - 1, mid, last);
		}
	}

	public static void mergeSort(int[] array) {
		int length = array.length;
		processMergeSort(array, 0, length - 1);
	}

	public static void main(String[] args) {
		int[] a = new int[] { 2, 55, 6, 7, 11, 34, 33, 3333, 0, -1, -2, 34344,
				33, 21, 14 };
		int[] b = new int[99999];
		for (int i = 0; i < 99999; i++) {
			b[i] = 99999 - i;
		}
		long start = System.currentTimeMillis();
		mergeSort(b);
		long end = System.currentTimeMillis();
		System.out.println("耗时：" + (end - start) + "毫秒");
		// print(b);
	}

}