void QSort( int l, int r, int *a ) { 
  int i = l, j = r;
  int x = a[l + rand() % (r - l + 1)]; 

  /** Do partition, a[l..r] --> "<= x", ">= x" */
  while (i <= j) {
    while (a[i] < x) i++;
    while (a[j] > x) j--;
    if (i <= j) swap(a[i++], a[j--]);     
  }

  /** Do recursion */
  if (l < j) QSort(l, j, a);
  if (i < r) QSort(i, r, a);
}