The Shell sort (named for its inventor, Donald Shell) is an improved insertion sort. Rather than always exchanging adjacent items-as in an insertion sort-the Shell sort can exchange items that are far apart in the array. The Shell sort arranges the array so that every hth item forms a sorted subarray in a decreasing sequence of values. For example, if h is 5, every fi fth item forms a sorted subarray. Ultimately, if h is 1, the entire array will be sorted. One possible sequence of h 's begins at n / 2 and halves n until it becomes 1. By using this sequence, and by replacing 1 with h and 0 with h - 1 in insertion Sort, we get the following function for the Shell sort:
Add a counter to the functions insertion Sort and shell Sort that counts the number of comparisons that are made. Run the two functions with arrays of various sizes. At what size does the difference in the number of comparisons become significant?