11 Jan 2020Shellsort is named after it's inventor, Donald Shell. If Mergesort works by repeatedly merging, and Quicksort works by repeatedly partitioning an array, then Shellsort works by repeatedly performing Insertion sort while varying the stepping of a subarray. Shellsort works in-place and is stable, like Insertion sort. But on large arrays it offers better performance than Insertion sort.
The panel above shows how arrays are displayed on this page, with columns illustrating the magnitude of the numbers.
In the array above, starting at the first entry, every fourth entry is taken to form a subarray, marked in blue. This subarray is sorted with Insertion sort, so that at the end, the green shaded boxes contain a sorted sequence of integers. This is done fairly quickly as there are only a few such entries in this small array. This is the basic step of operating Shellsort.
The procedure described on the previous panel can be repeated for all 4 possible starting positions, until every element in the array has participated in a sorting. At the end of this, the array is 4-sorted, where 4 is the stepping number of the subarrays. In general, a k-sorted array contains k subarrays, which are each sorted with respect to their peers in a subsequence with stepping k.
The entire Shellsort procedure works by starting with a sufficiently large parameter k, sorting the array to yield a k-sorted array, and then reducing k suitably and repeating. At the end of this procedure, k equals 1, which reduces to a normal Insertion sort. At this point the array is nearly completely sorted, and the Insertion sort pass proceeds quickly, leaving a fully sorted array.
The most obscure part of Shellsort is choosing the k values. Here we are using a standard scheme where the next larger k value is derived from the formula k = 3k + 1. Starting at 1 we compute such values until the size of the array would be surpassed, then start with this largest k value. After each k-sorting the next smaller k value is used, in this case yielding the sequence 13, 4, 1.
On this panel we start with a strictly descending array as input. This is harder to sort for some algorithms than purely random data. As you can see, Shellsort handles this case rather well. The sorting time is not much above the random input case we saw previously.
This panel shows Shellsort working on a larger array of 101 numbers, at a higher speed of animation. With this size of array, the initial k value is calculated as 40.
So far, Shellsort probably doesn't seem very fast. But it does have a speed advantage over many other simple algorithms, such as Insertion sort. For comparison, on the panel above, we sort an array of the same size as the one on the previous panel, but with Insertion sort. For the first half of the array, Insertion sort seems to be winning, but for the entire array, Shellsort turns out to be faster. The larger the array is, the more pronounced this difference will be.