Source of 8.18.java

Structures and functions

  1: public void insertionSort()
  2: {
  3:    // If fewer than two items are in the list, there is nothing to do
  4:    if (length > 1)
  5:    {
  6:       assert firstNode != null;
  7: 
  8:       // Break chain into 2 pieces: sorted and unsorted
  9:       Node unsortedPart = firstNode.getNextNode();
 10:       assert unsortedPart != null;
 11:       firstNode.setNextNode(null);
 12: 
 13:       while (unsortedPart != null)
 14:       {
 15:          Node nodeToInsert = unsortedPart;
 16:          unsortedPart = unsortedPart.getNextNode();
 17:          insertInOrder(nodeToInsert);
 18:       } // end while
 19:    } // end if
 20: } // end insertionSort
 21: // Version 4.0