/** 
 * 歸并排序 
 *  
 * @author pengcx 
 *  
 */  
public class Merge extends Sort {  
  /** 歸并所需的輔助數(shù)組 */  
  private static Comparable[] aux;  
  
  public static void main(String[] args) {  
    String[] a = { "d", "a", "w", "b", "q" };  
    Merge.sort(a);  
    show(a);  
  }  
  
  public static void sort(Comparable[] a) {  
    aux = new Comparable[a.length];  
    sort(a, 0, a.length - 1);  
  }  
  
  /** 
  * 排序數(shù)組的a[lo]至a[hi]元素 
  *  
  * @param a 
  *      數(shù)組a 
  * @param lo 
  *      最小元素位置lo 
  * @param hi 
  *      最大元素位置hi 
  */  
  private static void sort(Comparable[] a, int lo, int hi) {  
    if (hi <= lo) {  
      return;  
    }  
  
    // 計(jì)算數(shù)組中間位置  
    int mid = lo + (hi - lo) / 2;  
    // 排序數(shù)組a左邊的元素  
    sort(a, lo, mid);  
    // 排序數(shù)組a右邊的元素  
    sort(a, mid + 1, hi);  
    // 合并數(shù)組a左邊和右邊的元素  
    merge(a, lo, mid, hi);  
  }  
  
  /** 
  * 將數(shù)組a的a[lo]至a[mid]的元素與a[mid]至a[hi]的元素合并 
  *  
  * @param a 
  *      合并的數(shù)組a 
  * @param lo 
  *      最小數(shù)組元素lo 
  * @param mid 
  *      中間元素位置mid 
  * @param hi 
  *      最大元素位置hi 
  */  
  public static void merge(Comparable[] a, int lo, int mid, int hi) {  
    int i = lo, j = mid + 1;  
  
    for (int k = lo; k <= hi; k++) {  
      aux[k] = a[k];  
    }  
  
    for (int k = lo; k <= hi; k++) {  
      // 如果左邊的元素用盡，取右邊的元素  
      if (i > mid) {  
        a[k] = aux[j++];  
      }  
      // 如果右邊的元素用盡，取左邊的元素  
      else if (j > hi) {  
        a[k] = aux[i++];  
      }  
      // 如果右半邊的當(dāng)前元素小于左半邊的當(dāng)前元素，取右半邊元素  
      else if (less(aux[j], aux[i])) {  
        a[k] = aux[j++];  
      }  
      // 如果右半邊的當(dāng)前元素大于等于左半邊的當(dāng)前元素，取左半邊元素  
      else {  
        a[k] = aux[i++];  
      }  
    }  
  }  
}