In the questions below, assume that sorting refers to sorting into ascending order unless specied otherwise.

Consider the array [15 14 13 12 11 10 9 8 7 6 5 4 3 2 1]. Carry out a Shell sort on the array with subarrays defined by the values h_1 = 1, h_2 = 3, h_3 =5. (That is, sort in the same way as in the lecture slide example: split into 5 subarrays and do a 5-sort; then split into 3 subarrays and do a 3-sort; then do a 1-sort on the whole array.) Determine the total number of comparisons (between elements of the array) made during the Shell sort in (1a) above. Determine the total number of comparisons that would be made if an insertion sort were carried out on the whole array from (1a) above. (Harder) Consider an array in descending order [n n - 1 n - 2... 1] for some n divisible by 5; that is, n = 5k for some integer k greaterthanorequalto 1. Determine the total number of comparisons that would be made in a Shell sort with h_1 = 1,h_2 = 5 (that is, a 5-sort followed by a 1-sort). Express your answer as a function of k. Determine the total number of comparisons that would be made by an insertion sort. Express your answer as a function of k. Is the Shell sort always as good as or better than insertion sort on this type of array, for any valid n? Why or why not? The last part of the question is harder, but have a go at it anyway. For (1a), format your answer in the same way as in the lecture slides/textbook. A text file containing the answers will be satisfactory; if you submit a Word document, use a fixed-width font like Courier so that alignment of subarrays is clear