Problems

Implement a method that will sort a given array using the insertion sort algorithm $($given below$).$

Write a driver program to test the insertion algorithm implemented in Problem $1.$ Open the input files from Canvas and store them in separate arrays. Sort these arrays using insertion sort.

Test the program for the different size input files provided in Canvas.

Record the runtime for insertion sort on various sized arrays by using the provided files. Comnifent on how the execution time of insertion sort varies with size of the input array. Use a table or plot to summarize the results and document your observations and explanations in the report.

INSERTION$-$SORT $(A)$

for $j=2$ to $A.$length

key $=A[j]$

$//$ Insert $A[j]$ into the sorted sequence $A[1$dotsj$-1].$

$i=j-1$

while $i>0$ and $A[i]>$key

$A[i+1]=A[i]$

$i=i-1$

$A[i+1]=$key

Note: The above pseudo code assumes that the array indexing is starting from $1.$ If you are using a programming language that uses array indexing starting from $0,$ you must modify the pseudo code accordingly.