public void insertionSort()
{
   // If fewer than two items are in the list, there is nothing to do
   if (length > 1)
   {
      assert firstNode != null;

      // Break chain into 2 pieces: sorted and unsorted
      Node unsortedPart = firstNode.getNextNode();
      assert unsortedPart != null;
      firstNode.setNextNode(null);

      while (unsortedPart != null)
      {
         Node nodeToInsert = unsortedPart;
         unsortedPart = unsortedPart.getNextNode();
         insertInOrder(nodeToInsert);
      } // end while
   } // end if
} // end insertionSort
// Version 4.0