Implement a program that measures the performance of the insertion sort algorithm described in Special Topic 14.2.

Data from special topic 14.2

Special Topic 14.2 Insertion Sort Insertion sort is another simple sorting algorithm. In this algorithm, we assume that the initial sequence a[0] a[1]... a[k] of an array is already sorted. (When the algorithm starts, we set k to 8.) 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 complete. For example, suppose we start with the array 11 9 16 5 7 Of course, the initial sequence of length 1 is already sorted. We now add a[1], which has the value 9. The element needs to be inserted before the element 11. The result is 9 11 16 5 7 Next, we add a[2], which has the value 16. This element does not have to be moved. 9 11 16 5 7 We repeat the process, inserting a[3] or 5 at the very beginning of the initial sequence. 5 9 11 16 7 Finally, a [4] or 7 is inserted in its correct position, and the sorting is completed. The following class implements the insertion sort algorithm: