//IntListSort.java
class IntListSort {
  static IntList sort(IntList list) {
    IntList sorted = new IntList();
    IntListIterator listIter = list.iterator();
    while (listIter.hasNext()) {
      // select the next item to be inserted
      int newItem = listIter.next();
      IntListIterator sortedIter = sorted.iterator();
      IntListIterator previous = null;
      // loop until a bigger item is found in sorted
      while (sortedIter.hasNext() &&
                newItem > sortedIter.next()) 
      {
        previous = sortedIter.copy();
      }
      // insert before the bigger item which we do
      // by inserting after the element before it
      if (previous == null) // insert at head
        previous = sorted.iterator();
      sorted.insert(previous, newItem);
    }
    return sorted;
  }
}