import java.util.*;
/** Sortable vectors */

public class SortableVector extends Vector {


  void sort(int lo0, int hi0){
    int lo = lo0;
    int hi = hi0;
    if (lo >= hi) {
      return;
    }
    Comparable mid = (Comparable)elementData[(lo + hi) / 2];
    while (lo < hi) {
      while (((Comparable)elementData[lo]).lessThan(mid) && lo < hi0) {
        lo++;
      }
      while (mid.lessThan((Comparable)elementData[hi])&& hi > lo0 ) {
        hi--;
      }
      if (lo < hi) {
        Object T = elementData[lo];
        elementData[lo] = elementData[hi];
        elementData[hi] = T;
        hi--;
        lo++;
      }
    }
    if (hi < lo) {
      int T = hi;
      hi = lo;
      lo = T;
    }
   sort(lo0, lo);
    sort(lo == lo0 ? lo+1 : lo, hi0);
  }
 
  public void sort(){
    sort(0,elementCount-1);	 
  }

  void isort(int lo0, int hi0, int[] ind){
    int lo = lo0;
    int hi = hi0;
    if (lo >= hi) {
      return;
    }
    Comparable mid = (Comparable)elementData[ind[(lo + hi) / 2]];
    while (lo < hi) {
      while (((Comparable)elementData[ind[lo]]).lessThan(mid) && lo < hi0) {
        lo++;
      }
      while (mid.lessThan((Comparable)elementData[ind[hi]])&& hi > lo0 ) {
        hi--;
      }
      if (lo < hi) {
        int t = ind[lo];
        ind[lo] = ind[hi];
        ind[hi] = t;
        hi--;
        lo++;
      }
    }
    if (hi < lo) {
      int T = hi;
      hi = lo;
      lo = T;
    }
    isort(lo0, lo,ind);
    isort(lo == lo0 ? lo+1 : lo, hi0,ind);
  }

  public int[] isort(){
    int[] ind = new int[elementCount];
    for(int i = 1; i < elementCount; i++) {
      ind[i] = i;
    }
    isort(0,elementCount-1,ind);
    return ind;
  }
}