Chapter 7, Problem 4PP

Add a method insertionSort to the class ArraySorter, as given in Listing 7.10, mat performs an insertion sort of an array. To simplify this protect, our insertion sort algorithm will use an additional array. It copes elements from the original given array to this other array, inserting each element into its correct portion in the second array. This will usually require moving a number of elements in the array receiving the new elements. The algorithm in pseudocode is as follows:

Inserting into a sorted array

Insertion sort algorithm to sort an array

for (index = 0; index <a.length; index++)

Insert the value of a [index] into its correct position in the array temp, so that all the elements copied into the array temp so far are sorted.