Shellsort is a simple extension of insertion sort that gains speed by allowing exchanges of entries that are far apart. It works by producing partially sorted arrays that can be efficiently sorted, eventually by insertion sort. The idea is to rearrange the array to give it the property that taking every hth entry (starting anywhere) yields a sorted sequence. Such an array is said to be h-sorted.

By h-sorting for some large values of h, we can move entries in the array long distances and thus make it easier to h-sort for smaller values of h. Using such a procedure for any increment sequence of values of h that ends in 1 will produce a sorted array. That is the essence of shellsort.

For this assignment, create your own Shellsort. Your output should be similar to:

> more test.txt S O R T E X A M P L E > java ShellSort < test.txt

A E E L M O P R S T X