Lamuto partition

gistfile1.cpp

int Partition(int *a, int l, int r) {
  r--;
  int pivot = a[r];
  int i = l - 1;
  for (int j = l; j < r; j++)
    if (a[j] <=  pivot)
      swap(a[++i], a[j]);
  swap(a[++i], a[r]);
  return i;
}