Sorting algorithms - Data Structures and Problem Solving Using Java - page 360

roughly geometrically) will have a worst-case running time of at most
O ( N 3/2 ). 2 The average performance of the algorithm with these new incre-
ments is unknown but seems to be O ( N 5/4 ), based on simulations.

A third sequence, which performs well in practice but has no theoretical
basis, is to divide by 2.2 instead of 2. This divisor appears to bring the aver-
age running time to below O ( N 5/4 )—perhaps to O ( N 7/6 )—but this case is
completely unresolved. For 100,000 to 1,000,000 items, it typically improves
performance by about 25 to 35 percent over Shell's increments, although
nobody knows why. A Shellsort implementation with this increment sequence
is coded in Figure 8.7. The complicated code at line 8 is necessary to avoid
setting gap to 0. If that happens, the algorithm is broken because we never see
a 1-sort. Line 8 ensures that, if gap is about to be set to 0, it is reset to 1.
The entries in Figure 8.6 compare the performance of insertion sort and
Shellsort, with various gap sequences. We could easily conclude that
Shellsort, even with the simplest gap sequence, provides a significant
improvement over the insertion sort, at a cost of little additional code com-
plexity. A simple change to the gap sequence can further improve perfor-
mance. More improvement is possible (see in Exercise 8.25). Some of these
improvements have theoretical backing, but no known sequence markedly
improves the program shown in Figure 8.7.

Dividing by 2.2
gives excellent
performance in
practice.

1 /**
2 * Shellsort, using a sequence suggested by Gonnet.
3 */
4 public static <AnyType extends Comparable<? super AnyType>>
5 void shellsort( AnyType [ ] a )
6 {
7 for( int gap = a.length / 2; gap > 0;
8 gap = gap == 2 ? 1 : (int) ( gap / 2.2 ) )
9 for( int i = gap; i < a.length; i++ )
10 {
11 AnyType tmp = a[ i ];
12 int j = i;
13
14 for( ; j >= gap && tmp.compareTo( a[j-gap] ) < 0; j -= gap )
15 a[ j ] = a[ j - gap ];
16 a[ j ] = tmp;
17 }
18

}

figure 8.7
Shellsort implementation

2. To appreciate the subtlety involved, note that subtracting 1 instead of adding 1 does not
work. For instance, if N is 186, the resulting sequence is 93, 45, 21, 9, 3, 1, which all share
the common factor 3.