import java.util.Arrays;

public class MergeSort {
 public static void mergeSort(int[] a, int start, int end) {
  if (start < end) {
   int mid = (start + end) / 2;
   mergeSort(a, start, mid);
   mergeSort(a, mid + 1, end);

   merge(a, start, mid, end);
  }
 }

 private static void merge(int[] a, int start, int mid, int end) {
  int[] temp = new int[a.length];
  int i = start, j = mid + 1, k = start;
  while (i <= mid && j <= end) {
   if (a[i] < a[j]) {
    temp[k] = a[i];
    k++;
    i++;
   } else {
    temp[k] = a[j];
    k++;
    j++;
   }
  }
  if (i > mid) {
   while (j <= end) {
    temp[k] = a[j];
    k++;
    j++;
   }
  } else {
   while (i <= mid) {
    temp[k] = a[i];
    k++;
    i++;
   }
  }
  for (k = start; k <= end; k++) {
   a[k] = temp[k];
  }
 }

 /**
  * 非遞歸版本
  * mergeSort sort the int array a
  * @param a
  *  the array to be sorted
  **/
 public static void mergeSort(int[] a) {
  int[] b = new int[a.length];
  int s = 1;
  while (s < a.length) {
   mergePass(a, b, s); //合并到數(shù)組b
   s += s;
   mergePass(b, a, s); //合并到數(shù)組a
   s += s;
  }
 }

 /**
  * mergePass用于合并排好序的相鄰數(shù)組段，具體的合并算法由merge來實現(xiàn)
  *   @param x
  *  the src
  * @param y
  *  the des
  * @param s
  *  the size of merge array
  **/
 public static void mergePass(int[] x, int[] y, int s) {
  int i = 0;
  while (i < x.length - 2 * s) {
   //合并大小為s的相鄰2段子數(shù)組
   merge(x, y, i, i + s - 1, i + 2 * s - 1);
   i += 2 * s;
  }
  //剩下的元素少于2 * s
  if (i + s < x.length) {//剩下的元素小于 2 * s 但大于 s
   merge(x, y, i, i + s - 1, x.length - 1);
  } else {
   //剩下的元素小于 s ,復(fù)制到y(tǒng)
   for (int j = i; j < x.length; j++) {
    y[j] = x[j];
   }
  }
 }

 /**
  * 合并c[l:m]和c[m+1:r]到d[l:r]
  *
  * @param c
  *  the src array
  * @param d
  *  the des array
  * @param l
  *  the start
  * @param m
  *  the mid
  * @param r
  *  the end
  *
  **/
 public static void merge(int[] c, int[] d, int l, int m, int r) {
  int i = l;
  int j = m + 1;
  int k = l;
  while ((i <= m) && (j <= r)) {
   if (c[i] <= c[j]) {
    d[k++] = c[i++];
   } else {
    d[k++] = c[j++];
   }
  }
  if (i > m) {
   for (int q = j; q <= r; q++) {
    d[k++] = c[q];
   }
  } else {
   for (int q = i; q <= m; q++) {
    d[k++] = c[q];
   }
  }
 }

 public static void main(String[] args) {
  int[] a = { 3, 4, 1, 5, 9, 3, 2, 8, 10 };
  int[] b = { 3, 4, 1, 5, 9, 3, 2, 8, 10 };
  mergeSort(a, 0, a.length - 1);
  mergeSort(b);
  System.out.println(Arrays.toString(a));
  System.out.println(Arrays.toString(b));
 }
}