interface Comparator {
  /** return < 0 for less, 0 for equal, > 0 for greater **/
  public int compare(Object a, Object b);
}

// sample implementation
 class StringComparator implements Comparator {
  public int compare(Object a, Object b) {
    if (!(a instanceof String && b instanceof String))
      throw new Error("Incompatable types in compare?");
    String x = (String) a;
    String y = (String) b;
    return x.compareTo(y);
  }
}


class SortableArray {
  protected Object array_[]; // the elements
  protected int count_;      // number of slots actually used
  // ... other methods omitted ...

  public void sort(Comparator cmp) { quickSort(0, count_ - 1, cmp); }

  protected void quickSort(int lo, int hi, Comparator cmp) {

    if (lo >= hi) return;

    //  Use median-of-three(lo, mid, hi) to pick a partition. 
    //  Also swap them into relative order while we are at it.
  
    int mid = (lo + hi) / 2;
  
    if (cmp.compare(array_[lo], array_[mid]) > 0) 
      swap(lo, mid);
    if (cmp.compare(array_[mid], array_[hi]) > 0) {
      swap(mid, hi);
      if (cmp.compare(array_[lo], array_[mid]) > 0) 
        swap(lo, mid);
    }
    
    int left = lo+1;           // start one past lo since already handled lo
    int right = hi-1;          // similarly
    if (left >= right) return; // if three or fewer we are done
    
    Object partition = array_[mid];
    
    for (;;) {
      
      while (cmp.compare(array_[right], partition) > 0) 
        --right;
      
      while (left < right && cmp.compare(array_[left], partition) <= 0) 
        ++left;
      
      if (left < right) {
        swap(left, right);
        --right;
      }
      else break;

    }
    
    quickSort(lo, left, cmp);
    quickSort(left+1, hi, cmp);
    
  }

  /* swap array_[i] and array_[j] */
  protected final void swap(int i, int j) { 
    Object tmp = array_[i]; 
    array_[i] = array_[j]; 
    array_[j] = tmp; 
  }

  // a sample extended version with a couple of coding tweaks:
  //   (1) Use a stack instead of recursive calls
  //   (2) hard-code swaps instead of calling swap method

  // Since the largest half is always chosen to be pushed, there can be
  // no more than lg N + 1 pushed halves. Given that indexes
  // are signed 32 bits, there can be no more than 2^31 elements. So:

  static final int STACK_SIZE = 64; // for 32 bit int indices

  protected void quickSortV2(int lo, int hi, Comparator cmp) {
    int[] stack = new int[STACK_SIZE];
    int sp = 0;

    if (lo >= hi) return;
    
    for (;;) {

      //  Use median-of-three(lo, mid, hi) to pick a partition. 
      //  Also swap them into relative order while we are at it.
      
      int mid = (lo + hi) / 2;
      
      if (cmp.compare(array_[lo], array_[mid]) > 0) {
        Object t = array_[lo]; array_[lo] = array_[mid]; array_[mid] = t;
      }
      if (cmp.compare(array_[mid], array_[hi]) > 0) {
        Object t = array_[mid]; array_[mid] = array_[hi]; array_[hi] = t;
        if (cmp.compare(array_[lo], array_[mid]) > 0) {
          Object u = array_[lo]; array_[lo] = array_[mid]; array_[mid] = u;
        }
      }
      
      int left = lo+1;           // start one past lo since already handled lo
      int right = hi-1;          // similarly
      
      if (left >= right) {       // done, pop new ones
        if (sp > 0) {
          lo = stack[--sp];
          hi = stack[--sp];
        }
        else 
          return;
      }
      else {
        Object partition = array_[mid];
        
        for (;;) {
          
          while (cmp.compare(array_[right], partition) > 0) {
            --right;
          }
          
          while (left < right && cmp.compare(array_[left], partition) <= 0) {
            ++left;
          }
          
          if (left < right) {
            Object t = array_[left]; array_[left] = array_[right]; array_[right] = t;
            --right;
          }
          else
            break;
        }
        
        right = left + 1; // force to be first of right side

        // iterate the smaller side; push larger
        // note that given above code at least one side must have > 1 element

        if (right >= hi) // if empty, ignore
          hi = left;
        else if (lo >= left)
          lo = right;
        else if (left - lo > hi - right) {
          stack[sp++] = left;
          stack[sp++] = lo;
          lo = right;
        }
        else {
          stack[sp++] = hi;
          stack[sp++] = right;
          hi = left;
        }
      }
    }
  }

  // another sample extended version with a couple of coding tweaks:
  //   (1) Use iteration instead of recursive call for one side
  //   (2) Exit after one pass if they are all in order
  //   (3) Use insertion sort for small subsets
  //   (4) hard-code swaps instead of calling swap method

  static final int INSERTION_SORT_THRESHOLD = 8;

  protected void quickSortV3(int lo, int hi, Comparator cmp) {

    while (lo < hi) {

      // Simultaneously check if in order and, if small use insertion sort
      boolean useInsertion = (hi - lo + 1) <= INSERTION_SORT_THRESHOLD;
      int i = lo + 1;
      for (;;) {
        Object x = array_[i];
        int k = i - 1;
        while (k >= lo && cmp.compare(x, array_[k]) < 0) {
          array_[k+1] = array_[k];
          --k;
        }
        array_[k+1] = x;

        if (i == hi) // done
          return;
        else if (!useInsertion && k + 1 != i) // if not in order use QS
          break;
        else
          ++i;
      }

      //  Use median-of-three(lo, mid, hi) to pick a partition. 
      //  Also swap them into relative order while we are at it.
      
      int mid = (lo + hi) / 2;
      
      if (cmp.compare(array_[lo], array_[mid]) > 0) {
        Object t = array_[lo]; array_[lo] = array_[mid]; array_[mid] = t;
      }
      if (cmp.compare(array_[mid], array_[hi]) > 0) {
        Object t = array_[mid]; array_[mid] = array_[hi]; array_[hi] = t;
        if (cmp.compare(array_[lo], array_[mid]) > 0) {
          Object u = array_[lo]; array_[lo] = array_[mid]; array_[mid] = u;
        }
      }
      
      int left = lo+1;           // start one past lo since already handled lo
      int right = hi-1;          // similarly
      if (left >= right) return; // if three or fewer we are done

    
      Object partition = array_[mid];

      for (;;) {
        
        while (cmp.compare(array_[right], partition) > 0) 
          --right;
        
        while (left < right && cmp.compare(array_[left], partition) <= 0) 
          ++left;
        
        if (left < right) {
          Object t = array_[left]; array_[left] = array_[right]; array_[right] = t;
          --right;
        }
        else break;
      }

      // iterate the smaller side; recurse on larger
      if (left - lo > hi - left) {
        if (lo < left) quickSortV3(lo, left, cmp);
        lo = left + 1;
      }
      else {
        if (left+1 < hi) quickSortV3(left+1, hi, cmp);
        hi = left;
      }

    }
    
  }

}