Shellsort (more accurately Shells sort) is an important sorting algorithm that works by applying insertion sort to each of several interleaving sublists of a given list. On each pass through the list, the sublists in question are formed by stepping through the list with an increment hi taken from some predefined decreasing sequence of step sizes, h1> . . .>hi > . . . > 1, which must end with 1. (The algorithm works for any such sequence, though some sequences are known to yield a better efficiency than others. For example, the sequence 1, 4, 13, 40, 121, . . . , used, of course, in reverse, is known to be among the best for this purpose)

a. Apply shellsort to the list S, H, E, L, L, S, O, R, T, I, S, U, S, E, F, U, L

b. Is shellsort a stable sorting algorithm?

c. Implement shellsort, straight insertion sort, selection sort, and bubble sort in the language of your choice and compare their performance on random arrays of sizes 10n for n = 2, 3, 4, 5, and 6 as well as on increasing and decreasing arrays of these sizes.