// quick sort implementation

template <class Item>
int partition(Item a[], int l, int r) {
  int i = l-1, j = r;
  Item v = a[r]; // pivot
  while (1) {
    while (a[++i] < v);
    while (v < a[--j]) { if (j == l) break; }
    if (i >= j) break; else exch(a[i], a[j]);
  }
  a[r] = a[i];
  a[i] = v;
  return i;
}

# include "STACKlist.cpp"

inline void push2(STACK<int>&s, int A, int B) {
  s.push(A); s.push(B); return;
}

template <class Item>
void sort(Item a[], int l, int r) {
  STACK<int> s(100); // list implemementation: 100 is ignored
  int i;

  push2 (s, l, r);

  while (!s.empty()) {
    r = s.pop();
    l = s.pop();
    if (r <= l) continue;;
    // r > l
    i = partition(a, l, r);

    if (i-l > r-i) {
      push2(s, l, i-1);
      push2(s, i+1, r);
    } else {
      push2(s, i+1, r);
      push2(s, l, i-1);
    }
  }

  return;
}