Add a method insertionSort to the class ArraySorter, as given in Listing 7.10, that performs an insertion sort of an array. To simplify this project, our insertion sort algorithm will use an additional array. It copies elements from the original given array to this other array, inserting each element into its correct position 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:

Question

Insertion sort algorithm to sort an array a
```
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.
Copy all the elements from temp back to a.

The array temp is partially filled and is a local variable in the method sort.


1. This project also requires an extension of the algorithm in the problem statement. In these descriptions the word "up" is used to mean a higher subscript in the array. (It could just as easily be called "down;" the important thing is to use the directions consistently in all descriptions.) The sorted array, temp, is created one element at a time, then, when all elements have been inserted correctly, temp needs to be copied back into the original array:
For each element in the original array:
{
Get next value.
Find its insertion point:
{
Compare next value to each element of temp, in order, starting at the lowest.
The insertion point is found either when next value > element in temp,
or the end of temp is reached.
}
Starting at the end of temp and working backward through the insertion point,
move the elements in temp up one place. (You need to start at the top and
work backward to avoid overwriting data in temp, and the value at the
insertion point needs to be moved so next value can be inserted.)
Insert next value into temp at the insertion point.
}
Copy temp array into original array: the original array is now sorted.
Following the approach in the text, an additional class, InsertionSortDemo, is used to demonstrate the bubble sort method with a sample array.

Answer 1

See the code in InsertionSort.java and InsertionSortDemo.java.