Polymorphism - Java Software Solutions: Foundations of Program Design - page 511

Insertion Sort
The Sorting class also contains a method that performs an insertion sort on an
array of Comparable objects. If used to sort the array of Contact objects in the
PhoneList program, it would produce the same results as the selection sort did.
However, the logic used to put the objects in order is different.
The insertion sort algorithm sorts a list of values by repetitively inserting a par-
ticular value into a subset of the list that has already been sorted. One at a time,
each unsorted element is inserted at the appropriate position in that sorted subset
until the entire list is in order.
The general strategy of insertion sort is: Begin with a “sorted” list contain-
ing only one value. Sort the first two values in the list relative to each other by
exchanging them if necessary. Insert the list's third value into the appropriate
position relative to the first two (sorted) values. Then insert the fourth value into
its proper position relative to the first three values in the list. Each time an inser-
tion is made, the number of values in the sorted subset increases by one. Continue
this process until all values are inserted in their proper places, at which point the
list is completely sorted.
The insertion process requires that the other values in the array shift to make
room for the inserted element. Figure 10.3 demonstrates the behavior of the inser-
tion sort algorithm with integers.

3 is sorted.
Shift nothing. Insert 9.

3 9 6 1 2

3 and 9 are sorted.
Shift 9 to the right. Insert 6.

3 9 6 1 2

3, 6 and 9 are sorted.
Shift 9, 6, and 3 to the right. Insert 1.

3 6 9 1 2

1, 3, 6 and 9 are sorted.
Shift 9, 6, and 3 to the right. Insert 2.

1 3 6 9 2

All values are sorted.

1 2 3 6 9

FIGURE 10.3 Insertion sort processing