public class Exercise7b
{
  // partitions a[left..right] by element at pivot position
  // returns position that separates the parts
  public static int partition(int[] a, int left, int right, int pivot)
  { 
    int v = a[pivot];
    a[pivot] = a[right];
    int i = left;
    int j = right-1;
    while (i <= j)
    { 
      if (a[i] < v)
        i = i+1;
      else if (a[j] >= v)
        j = j-1;
      else 
      {
        int t = a[i]; a[i] = a[j]; a[j] = t;
        i = i+1; j = j-1;
      }
    }
    a[right] = a[i];
    a[i] = v;
    return i;
  }

  // sorts a[left..right]
  public static void sort(int[] a, int left, int right)
  {
    if (left >= right) return;
    int p = partition(a, left, right, (left+right)/2);
    sort(a, left, p-1);
    sort(a, p+1, right);
  }

  // sorts a in ascending order
  public static void sort(int[] a)
  {
    sort(a, 0, a.length-1);
  }
}