Repeat Practice Program 1, but instead write a method insertionSort that performs an insertion sort, as described in Programming Project 4 of Chapter 7.

As with the previous project, an easy way to develop the program is to start with the insertion sort code for an array, Chapter 7 Programming Project 4. Note, however, that the list code, unlike that for the array, does not need a helper method to move the elements when a new element is added to the temporary list; the ArrayList class has a method, add(int, T), that does it for you.

See the code in StringInsertionSort.java and StringInsertionSortDemo.java.