Write a program InsertionSortDemo.java that demonstrates the insertion sort algorithm. That program should include a static method .sort() that takes an int[] array as a parameter and sorts it using selection sort. The sort method uses the next two methods as part of its operation.
A review of the Insertion Sort algorithm:
Begin with an array of values a[0], a[1], a[2], ... a[n]
Consider the elements to the right to be unsorted (the "tail" of the array), and a growing number of elements to the left (the "head" of the array) to be sorted.
Examine the first element n = 0 in the array. This single element can be considered to be sorted, because it's the only element in the left, sorted end of the array.
Proceed to n + 1, and look at a[n + 1]. Take that value and insert it into the correct position in the sorted "head" of the array. (Ie., does it go before a[0] or after?) Check elements to the left of this element in the sorted head until you find the correct location to "insert" this value and place it there. The head of the array should still have all of its values sorted, with this most recent one in its correct position.
Get the next number in the array, a[n + 2], examine it, and insert it into its correct position in the sorted array, being sure to shift all the other elements down again.
Proceed until the entire array of elements has been inserted into their correct positions in the array.