of an array is already sorted. (When the algorithm starts, we set k to 0 .) We
enlarge the initial sequence by inserting the next array element, a[k + 1] , at the
proper location. When we reach the end of the array, the sorting process is
For example, suppose we start with the array
Of course, the initial sequence of length 1 is already sorted. We now add a ,
which has the value 9. The element needs to be inserted before the element 11. The
Next, we add a  , which has the value 16. As it happens, the element does not
have to be moved.
We repeat the process, inserting a or 5 at the very beginning of the initial
Finally, a or 7 is inserted in its correct position, and the sorting is completed.
The following class implements the insertion sort algorithm:
public class InsertionSorter
Constructs an insertion sorter.
@param anArray the array to sort
public InsertionSorter(int anArray)
a = anArray;