in python, Implement the insertion sort algorithm (Algorithm 1). Set n = 1000. Populate your input test array with random elements. (a) (10 points) Test its performance in the best-case where entire array is already sorted you can do this by calling your languages sort routine on the input array, before calling insertion sort on it. (b) (10 points) Test its performance in the worst case by passing a reverse-sorted array as input. (c) (10 points) Manually populate your array with a fixed, same value for all elements (dont use the random number generator this time). Run insertion sort on it. (d) (15 points) Now, modify the code of insertion sort so that it sorts the array in reverse order. Test the worst-case on it the worst-case here is triggered by passing the sorted array as input. In all 4 cases of insertion sort, plot the run-time on a single graph.

Algorithm 1: Insertion sort Input : Unsorted array A Output: A with sorted elements 1 for j = 2 to A.length do 2 key = A[j] /* Insert A[j] into sorted sequence A[1..j 1] */ 3 i = j 1 4 while i > 0 and A[i] > key do 5 A[i + 1] = A[i] 6 i = i 1 7 end 8 A[i + 1] = key 9 end 10 return A