Shell sort (or Shellsort) is one of the oldest sorting algorithms, named after its inventor D.L. Shell [Sh]. It is fast, easy to understand and easy to implement. However, its complexity analysis is a little more sophisticated. It is easy to develop an intuitive sense of how this algorithm works, but often difficult to analyze its execution time.
Shell sort is really just an extension of insertion sort, with two observations in mind:
Consider a small value that is initially stored in the wrong end of the array. Using insertion sort, it will take roughly n comparisons and exchanges to move this value all the way to the other end of the array. With Shell sort, we'll first move values using giant step sizes, so a small value will move a long way towards its final position, with just a few comparisons and exchanges.
The idea of Shell sort can be illustrated in the following way:
Example: Let
3 7 9 0 5 1 6 8 4 2 0 6 1 5 7 3 4 9 8 2be the data sequence to be sorted. First, it is arranged in an array with 7 columns (left), then the columns are sorted (right):
3 7 9 0 5 1 6 3 3 2 0 5 1 5 8 4 2 0 6 1 5 -> 7 4 4 0 6 1 6 7 3 4 9 8 2 8 7 9 9 8 2Data elements 8 and 9 have now already come to the end of the sequence, but a small element (2) is also still there. In the next step, the sequence is arranged in 3 columns, which are again sorted:
3 3 2 0 0 1 0 5 1 1 2 2 5 7 4 3 3 4 4 0 6 -> 4 5 6 1 6 8 5 6 8 7 9 9 7 7 9 8 2 8 9Now the sequence is almost completely sorted. When arranging it in one column in the last step, it is only a 6, an 8 and a 9 that have to move a little bit to their correct position.
Actually, the data sequence is not arranged in a two-dimensional array, but held in a one-dimensional array that is indexed appropriately. For instance, data elements at positions 0, 5, 10, 15 etc. would form the first column of an array with 5 columns. The "columns" obtained by indexing in this way are sorted with Insertion sort, since this method has a good performance with presorted sequences.
The following program sorts an array a from index position 0 through n-1. The number of columns used for arranging data in each step is in array cols. Thus, data are arranged in 1391376 columns in the first step and in one column in the last step. (Note that essentially nothing is done if the number of columns h is larger than the number of data elements n.) Each column is sorted by Insertionsort. First, data of the second row (beginning at i = h) are sorted to the correct position in their column, then data of the third row (when i reaches value 2h) etc.
The following Java program implements Shell sort.
Algorithm Shellsort
void shellsort (int[] a, int n)
{
int i, j, k, h, v;
int[] cols= {1391376, 463792, 198768, 86961, 33936, 13776, 4592,
1968, 861, 336, 112, 48, 21, 7, 3, 1};
for (k=0; k<16; k++)
{
h=cols[k];
for (i=h; i=h && a[j-h]>v)
{
a[j]=a[j-h];
j=j-h;
}
a[j]=v;
}
}
}
The correctness of the algorithm follows from the fact that in the last step (with h = 1) an ordinary Insertionsort is performed on the whole array. But since data are presorted by the preceding steps (h = 3, 7, 21, ...) only few Insertionsort steps are sufficient. How many exactly depends on the sequence of h's (denoted as h-sequence). The h-sequence above is just one of several possible.With the h-sequence 1, 3, 7, 15, 31, 63, 127, ..., 2k - 1, ... Shellsort needs O(n3/2) steps for sorting a sequence of length n.
With the h-sequence 1, 2, 3, 4, 6, 8, 9, 12, 16, ..., 2p3q, ... Shellsort needs O(n·log(n)2) steps for sorting a sequence of length n.
Thus it requires fewer than O(n²) comparisons and exchanges in the worst case.