Suppose that you want to perform a Shell sort on a linked chain.
a. Revise the method incrementalInsertionSort to work with a linked chain instead of an array.
b. Compare the performance of incrementalInsertionSort on an array with its performance on a linked chain.
c. Using the revised method, implement a Shell sort for a linked chain.
d. Find the run time required to sort n values in a linked chain for different values of n. (See the projects at the end of Chapter 4 for a description of how to time a block of Java code.) Graph the run time versus n.
e. Assuming that the performance of your sort is O(nk ), make an estimate for the value of k.