/** Insertion-sort for a doubly linked list of class DList.  */
  public static void sort(DList L) {
    if (L.size() <= 1) return; // L is already sorted in this case
    DNode pivot;	// pivot node 
    DNode ins;		// insertion point 
    DNode end = L.getFirst();	// end of run
    while (end != L.getLast()) {
      pivot = end.getNext();	// get the next pivot node
      L.remove(pivot);		// remove it
      ins = end;		// start searching from the end of the sorted run
      while (L.hasPrev(ins) &&
	     ins.getElement().compareTo(pivot.getElement()) > 0)
	ins = ins.getPrev();	// move left
      L.addAfter(ins,pivot);	// add the pivot back, after insertion point
      if (ins == end)		// we just added pivot after end in this case
	end = end.getNext();	// so increment the end marker
    }
  }