Problem
An algorithm called Shell Sort is inspired by Insertion Sort's ability to take advantage of the order of the elements in the list. In Shell Sort, the entire list is divided into noncontiguous subsists whose elements are a distance h apart for some number h. Each sub list is then sorted using Insertion Sort. During the next pass, the value of h is reduced, increasing the size of each sub list. Usually the value of each h is chosen to be relatively prime to its previous value. The final pass uses the value 1 for h to sort the list. Write an algorithm for Shell Sort, study its performance, and compare the result with the performance of Insertion Sort.