a sorting class named InsertionSort containing various versions of insertion sort algorithm.

• 21. In the package a032, new public class named InsertionSort, and a public class named InsertionSortTest.
• 22. In the InsertionSort class, design and implement the insertion sort method for an array of int-s, without calling other methods for performing operations (in-line all the code). The method is named sort.
• 23. In the InsertionSortTest, call the selection sort for some random arrays with length 0, 1, 2, 5 and 10. Check that they are sorted correctly (print them before and after).

Task 3: a class InsertionSortAnalysis containing time analysis methods.

• 31. In the a032 package, create a public class named InsertionSortAnalysis
• 32. In the class InsertionSortAnalysis, create two methods meanTime, and printMeanExecutionTimeGrowthTable, similar with the methods developed for selection sort.

Task 4: Analyze the execution time and memory needs for the insertion sort.

• 41. Explain in your own words which is the order of growth for the inserttion sort method.
• 42. Compute the growth table for some large arrays (at least 10 values for their length, with some large increment between them), draw a graph for the values.
• 43. Explain if the graph confirms or not the theoretical order of growth above.
• 44. Identify and compute the time for the best case and worse case scenarios (as execution time). Compare with their theoretical analysis.
• 45. Analyze the memory needs for the insertion sort method. Are they relevant? Why?