Sorting algorithms - Data Structures and Problem Solving Using Java - page 354

figure 8.2
Insertion sort
implementation

1 /**
2 * Simple insertion sort
3 */
4 public static <AnyType extends Comparable<? super AnyType>>
5 void insertionSort( AnyType [ ] a )
6 {
7 for( int p = 1; p < a.length; p++ )
8 {
9 AnyType tmp = a[ p ];
10 int j = p;
11
12 for( ; j > 0 && tmp.compareTo( a[ j - 1 ] ) < 0; j-- )
13 a[ j ] = a[ j - 1 ];
14 a[ j ] = tmp;
15 }
16 }

Insertion sort works as follows. In the initial state the first element, con-
sidering by itself, is sorted. In the final state all elements (assume that there
are N ) , considered as a group, are to have been sorted. Figure 8.3 shows that
the basic action of insertion sort is to sort the elements in positions 0 through p
(where p ranges from 1 through N - 1). In each stage p increases by 1. That is
what the outer loop at line 7 in Figure 8.2 is controlling.
When the body of the for loop is entered at line 12, we are guaranteed
that the elements in array positions 0 through p-1 have already been sorted
and that we need to extend this to positions 0 to p . Figure 8.4 gives us a
closer look at what has to be done, detailing only the relevant part of the
array. At each step the element in boldface type needs to be added to the
previously sorted part of the array. We can easily do that by placing it in a

figure 8.3
Basic action of
insertion sort (the
shaded part is sorted)

Array Position 012345

Initial State 859263

After a[0..1] is sorted 589263

After a[0..2] is sorted 589263

After a[0..3] is sorted 258963

After a[0..4] is sorted

256893

After a[0..5] is sorted 2 3 5 6 8 9