// Parallel merge sort: recursive halves composed with `[ A [] B ]`.

class MergeSort {
  void sort(int lo, int hi, int[] G) {
    if (lo < hi) {
      int mid = (lo + hi) / 2;
      [ sort(lo, mid, G) [] sort(mid+1, hi, G) ];
      Merge(lo, mid, hi, G);
    }
  }

  // Sequential aux: merge G[lo..mid] and G[mid+1..hi] in place using a
  // scratch copy B.
  void Merge(int lo, int mid, int hi, int[] G) {
    int[] B = new int[G.length];
    forall k in [lo..hi] : B[k] = G[k];
    int i = lo;
    int j = mid + 1;
    int k = lo;
    while (i <= mid && j <= hi) {
      if (B[i] <= B[j]) {
        G[k] = B[i];
        i = i + 1;
      } else {
        G[k] = B[j];
        j = j + 1;
      };
      k = k + 1;
    };
    while (i <= mid) {
      G[k] = B[i];
      i = i + 1;
      k = k + 1;
    };
    while (j <= hi) {
      G[k] = B[j];
      j = j + 1;
      k = k + 1;
    }
  }
}