An Introduction to Sorting - Data Structures and Abstractions with Java - page 202

Question 2 Trace the steps that an insertion sort takes when sorting the following array
into ascending order: 9 6 2 4 8.

Recursive Insertion Sort
8.12

You can describe an insertion sort recursively as follows. If you sort all but the last item in the array—a
smaller problem than sorting the entire array—you then can insert the last item into its proper position
within the rest of the array. The following pseudocode describes a recursive insertion sort:

Algorithm insertionSort(a, first, last)
// Sorts the array entries a[first] through a[last] recursively.

if ( the array contains more than one entry )
{

Sort the array entries a[first] through a[last - 1]
Insert the last entry a[last] into its correct sorted position within the rest of the array

}

We can implement this algorithm in Java as follows:

public static <T extends Comparable<? super T>>
void insertionSort(T[] a, int first, int last)

{

if (first < last)
{

// sort all but the last entry
insertionSort(a, first, last - 1);
// insert the last entry in sorted order
insertInOrder(a[last], a, first, last - 1);
} // end if
} // end insertionSort

8.13

The algorithm insertInOrder : first draft. The previous method can call the iterative version of
insertInOrder , given earlier, or the recursive version that we now describe. If the entry to insert is
greater than or equal to the last item in the sorted portion of the array, the entry belongs immediately
after this last item, as Figure 8-8a illustrates. Otherwise, we move the last sorted item to the next
higher position in the array and insert the entry into the remaining portion, as shown in Figure 8-8b.
We can describe these steps more carefully as follows:

Algorithm insertInOrder(anEntry, a, begin, end)
// Inserts anEntry into the sorted array entries a[begin] through a[end] .
// First draft.

if (anEntry >= a[end])
a[end + 1] = anEntry
else
{

a[end + 1] = a[end]
insertInOrder(anEntry, a, begin, end - 1)

}