package sorting; import java.util.*; public class Sort { public static int[] insertion_sort (int[] array) { /* * fill in your program */ return array; } /* * n: the size of the output array * k: the maximum value in the array */ public static int[] generate_random_array (int n, int k) { List list; int[] array; Random rnd; rnd = new Random(System.currentTimeMillis()); list = new ArrayList (); for (int i = 1; i  list; int[] array; list = new ArrayList (); for (int i = 1; i  array[i]) return false; } return true; } public static void print_array (int[] array) { for (int i = 0; i 

Problem Description Instructions. You are provided the skeleton code named Sort.java. The source file is available on Canvas in a folder named HW1. Please modify the skeleton code to solve the following tasks. Task 1 (80 pts). Implement the Insertion Sort algorithm as discussed in Lecture 1. (Hint: use the function checked sorted to check if your output is indeed sorted.) Task 2 (20 pts). Generate a report to discuss the time performance of the algorithm. Compare it with their theoretical time complexity as dis- cussed in the lecture. Plots and figures are encouraged to help draw the conclusion. See Figure 1 for an example of the plot. 60 50 -Selection Sort - Insertion Sort (avg) -Merge Sort 40 Time (in seconds) 30 20 10 0 0 1,000 2,000 3,000 4,000 5,000 6,000 7,000 8,000 9,000 10,000 Problem Size (number of items to be sorted) Figure 1: An example of the time performance plot Problem Description Instructions. You are provided the skeleton code named Sort.java. The source file is available on Canvas in a folder named HW1. Please modify the skeleton code to solve the following tasks. Task 1 (80 pts). Implement the Insertion Sort algorithm as discussed in Lecture 1. (Hint: use the function checked sorted to check if your output is indeed sorted.) Task 2 (20 pts). Generate a report to discuss the time performance of the algorithm. Compare it with their theoretical time complexity as dis- cussed in the lecture. Plots and figures are encouraged to help draw the conclusion. See Figure 1 for an example of the plot. 60 50 -Selection Sort - Insertion Sort (avg) -Merge Sort 40 Time (in seconds) 30 20 10 0 0 1,000 2,000 3,000 4,000 5,000 6,000 7,000 8,000 9,000 10,000 Problem Size (number of items to be sorted) Figure 1: An example of the time performance plot