//both a and b is ascend.
public void merge(int[] a, int[] b, int[] c){
  int i=0,j=0,k=0;
  while (i<=a.length && j<=b.length){
    if (a[i]<=b[i]){
      c[k++]=a[i++];
    }
    else{
      c[k++]=b[j++];
    }
  }
  while (i<=a.length){
    c[k++]=a[i++];
  }
  while (j<=b.length){
    c[k++]=b[j++];
  }
}

void sort(int[] a) {
  int[] aux = new int[a.length];  //辅助数组
  mergeSort(a, 0, a.length - 1, aux);
}

void mergeSort(int[] a, int lo, int hi, int[] aux) {
  if (hi <= lo)
    return;
  int mid = lo + (hi - lo) / 2;
  mergeSort(a, lo, mid, aux);
  mergeSort(a, mid + 1, hi, aux);
  merge(a, lo, mid, hi, aux);

}

void merge(int[] a, int lo, int mid, int hi, int[] aux) {
  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++];
    else if (aux[i] <= aux[j])
      a[k] = aux[i++];
    else
      a[k] = aux[j++];

  }
}

void sort(int[] a) {
  int N = a.length;
  int[] aux = new int[N];
  for (int sz = 1; sz < N; sz += sz) {
    for (int lo = 0; lo < N - sz; lo += sz + sz) {
      //在每轮归并中，最后一次归并的第二个子数组可能比第一个子数组要小
      merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1), aux);
    }
  }
}