(a)Construct an array of 25 elements containing the numbers 1 through 25 for which Shell Sort, with h-values {13, 4, 1} would use many compares than usual. In other words, construct an

array that would result in a worst-case runtime. How many compares does it require to be sorted?

HINT: Although you can search for a sequence of 25 values that causes the largest amount of compares, you will have to dedicate a daunting amount of time on doing that. Instead, search for a “bad” sequence going backwards: for ℎ = 1, place the 25 values such that the algorithm must swap the values a lot of times. Repeat the process for ℎ = 4 and ℎ = 13.

(b) Describe the best-case runtime for Shell Sort and the kind of input that would result in the best-case runtime. Justify your answer.