void quicksort(int first, int last)
    // sorts the subarray A[first .. last]
   {
    if(first < last) // otherwise there is at most one entry
     {
      int mid = (first+last)/2;
      swap(A[first],A[mid]);
      int pivot = A[first];
      int lo = first;
      int hi = last;
      // loop invariant holds here
      while(lo < hi) // the partition loop
       {
        // loop invariant holds here
        if(A[lo+1] <= pivot) lo++;
        if(lo < hi and A[hi] >= pivot) hi--
        if(lo < hi) and A[lo+1] > pivot and A[hi] < pivot)
         swap(A[lo+1],A[hi]);
       }
       // loop invariant holds
      swap(A[first],A[lo]);
      // now A[lo] = pivot
      quicksort(first,lo-1);
      quicksort(lo+1,last);
     }
   }
  
  int main()
   {
    quicksort(0,N-1);
    return 1;
   }