/** 
 * 归并排序 
 * 
 * @param ts 
 */ 
@SuppressWarnings("unchecked") 
public static <T extends Comparable<? super T>> void mergeSort(T[] ts) { 
 
  // 辅助空间 
  T[] tempArray = (T[]) new Comparable[ts.length]; 
 
  mergeSort(ts, tempArray, 0, ts.length - 1); 
} 
 
/** 
 * 递归 
 */ 
private static <T extends Comparable<? super T>> void mergeSort(T[] ts, T[] tempArray, int left, int right) { 
 
  if (left < right) { 
 
    int center = (left + right) / 2; 
 
    mergeSort(ts, tempArray, left, center); 
 
    mergeSort(ts, tempArray, center + 1, right); 
 
    // 左右合并 
    merge(ts, tempArray, left, center + 1, right); 
 
  } 
 
} 
 
/** 
 * 合并 
 */ 
private static <T extends Comparable<? super T>> void merge(T[] ts, T[] tempArray, int leftPos, int rightPos, int rightEnd) { 
  int leftEnd = rightPos - 1; 
  int temPos = leftPos; 
  int numElements = rightEnd - leftPos + 1; 
 
  while (leftPos <= leftEnd && rightPos <= rightEnd) 
    //比较放到辅助空间 
    if (ts[leftPos].compareTo(ts[rightPos]) <= 0) 
      tempArray[temPos++] = ts[leftPos++]; 
    else 
      tempArray[temPos++] = ts[rightPos++]; 
 
  while (leftPos <= leftEnd) 
    tempArray[temPos++] = ts[leftPos++]; 
 
  while (rightPos <= rightEnd) 
    tempArray[temPos++] = ts[rightPos++]; 
 
  //考回原数组,此处最好用System.arraycopy优化 
  for (int i = 0; i < numElements; i++, rightEnd--) 
    ts[rightEnd] = tempArray[rightEnd]; 
}