Algorithm 1 Insertion Sort 1: input: list L of n real numbers 2: for each element r E L from L(2) to L(n) do 3: while a is less than the element preceding r in L do 4: swap that element with r 5: end while 6: end for 7: return sorted list L Question 4: (40 points) Given a list of n distinct real numbers, a sorting algorithm seeks to reorder the list from smallest to largest. As comparisons between elements are relatively slow, sorting algorithms are commonly judged by the number of comparisons they make. Algorithm 1 is called inser- tion sort because each element in sequentially "inserted" into its proper place in the partially sorted list. We also provide a Python implementation of the insertion sort algorithm. a) Compute the maximum possible number of comparisons between list elements made by the deterministic insertion sort in Algorithm 1, in terms of n. b) To avoid the worst case, randomized insertion sort first randomly permutes the list, and then runs insertion sort. Let X be an integer random variable equal to the number of comparisons made by randomized insertion sort. Compute E[X] in terms of n. c) Monte Carlo sampling can be used to estimate the cumulative distribution function of X. Use Python to execute the provided randomized_insertion_sort 1000 times for lists of length n = 10, and plot the empirical CDF Fx(x). Compute and report the average number of comparisons across your 1000 Monte Carlo trials, and compare to the true expected value derived in part (b). d) Repeat part (c) for lists of length n = 100, and discuss how the distribution of comparisons changes as the list length grows