// Parallel quicksort: parallel-composed recursive partitions.

class QuickSort {
  void sort(int lo, int hi, int[] G) {
    if (lo < hi) {
      int p = Partition(lo, hi, G);
      [ sort(lo, p - 1, G) [] sort(p + 1, hi, G) ];
    }
  }

  // Sequential aux: in-place Lomuto partition on G[lo..hi]; returns the
  // pivot's final slot.
  int Partition(int lo, int hi, int[] G) {
    int pivot = G[hi];
    int i = lo - 1;
    int j = lo;
    while (j <= hi - 1) {
      if (G[j] <= pivot) {
        i = i + 1;
        int tmp = G[i];
        G[i] = G[j];
        G[j] = tmp;
      };
      j = j + 1;
    };
    int tmp = G[i + 1];
    G[i + 1] = G[hi];
    G[hi] = tmp;
    return i + 1;
  }
}