归并排序

package com.kingdee.gmis.algorithm;

public class MergeSort<T extends Comparable<T>> {

	public void mergeSort(T[] arrs) {
		this.mergeSort(arrs, 0, arrs.length - 1);
	}

	@SuppressWarnings("unchecked")
	private void mergeSort(T[] arrs, int l, int r) {
		this.mergeSort(arrs, (T[]) new Comparable[arrs.length], l, r);
	}

	private void mergeSort(T[] arrs, T[] tmpArrs, int l, int r) {
		if (l >= r) {
			return;
		}
		int midIdx = (l + r) / 2;
		mergeSort(arrs, tmpArrs, l, midIdx);
		mergeSort(arrs, tmpArrs, midIdx + 1, r);
		merge(arrs, tmpArrs, l, r, midIdx);
	}

	@SuppressWarnings("unchecked")
	private void merge(T[] arrs, T[] tmpArrs, int l, int r, int midIdx) {
		int i = l;
		int lStart = l;
		int rStart = midIdx + 1;
		while (i <= r) {
			while (lStart <= midIdx
					&& (rStart > r || arrs[lStart].compareTo(arrs[rStart]) <= 0)) {
				tmpArrs[i++] = arrs[lStart++];
			}
			while (rStart <= r
					&& (lStart > midIdx || arrs[rStart].compareTo(arrs[lStart]) <= 0)) {
				tmpArrs[i++] = arrs[rStart++];
			}
		}
		for (i = l; i <= r; i++) {
			arrs[i] = (T) tmpArrs[i];
		}
	}

}