package exp_sort;
public class MergeSort {
  /**
   * 相鄰兩個有序子序列的合并算法
   *
   * @param src_array
   * @param low
   * @param high
   * @param des_array
   */
  public static void Merge(int src_array[], int low, int high,
      int des_array[]) {
    int mid;
    int i, j, k;
    mid = (low + high) / 2;
    i = low;
    k = 0;
    j = mid + 1;
    // compare two list
    while (i <= mid && j <= high) {
      if (src_array[i] <= src_array[j]) {
        des_array[k] = src_array[i];
        i = i + 1;
      } else {
        des_array[k] = src_array[j];
        j = j + 1;
      }
      k = k + 1;
    }
    // if 1 have,cat
    while (i <= mid) {
      des_array[k] = src_array[i];
      k = k + 1;
      i = i + 1;
    }
    while (j <= high) {
      des_array[k] = src_array[j];
      k = k + 1;
      j = j + 1;
    }
    for (i = 0; i < k; i++) {
      src_array[low + i] = des_array[i];
    }
  }
  /**
   * 2-路歸并排序算法，遞歸實現(xiàn)
   *
   * @param src_array
   * @param low
   * @param high
   * @param des_array
   */
  public static void mergeSort(int src_array[], int low, int high,
      int des_array[]) {
    int mid;
    if (low < high) {
      mid = (low + high) / 2;
      mergeSort(src_array, low, mid, des_array);
      mergeSort(src_array, mid + 1, high, des_array);
      Merge(src_array, low, high, des_array);
    }
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array1[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
    int array2[] = new int[array1.length];
    mergeSort(array1, 0, array1.length - 1, array2);
    System.out.println("\n----------after sort-------------");
    for (int ii = 0; ii < array1.length; ii++) {
      System.out.print(array1[ii] + " ");
    }
    System.out.println("\n");
  }
}