3.3 SHELLSORT 71list. Each swap of elements will remove one or more of these inversions. For
example, when bubble sort does a comparison and finds two adjacent elements
out of order, it switches them, removing just one inversion. The same is true
for insertion sort because the movement of each larger element up one loca-
tion in the list is the removal of one inversion between it and the element we
are inserting. So, in bubble and insertion sort (O(N^2 ) sorts) each comparison
can result in the removal of exactly one inversion.
Because shellsort relies on insertion sort, it would seem that its analysis must
be the same, but when you consider that shellsort looks at sublists that are
interleaved with each other, one comparison can cause a swap that removes
more than just one inversion. On the first pass of Fig. 3.1, we compared 16
and 14, and because they were out of order they were swapped. By moving 16
from the first location to the ninth we removed 7 inversions of 16 with the val-
ues in locations 2 through 8 of the list. The analysis of shellsort gets compli-
cated because that same swap moved 14 from the ninth location to the first and
created seven new inversions, so that comparison didn’t help at all. If you look
at the swap of 7 and 4, you see the same thing. But overall, there are improve-
ments. On the first pass, we did eight comparisons and removed 36 inversions.
On the second pass, we did 16 comparisons and removed 20 inversions. On
the third pass, we did 19 comparisons and removed 24 inversions. And on the
last pass, we did 19 comparisons and removed the last 10 inversions. This is a
total of 62 comparisons. If we just considered the average cases for the inser-
tion sort calls that we did, you would still calculate 152 comparisons.
A complete analysis of the shellsort algorithm is very complex and beyond
the scope of this book. With the sequence of increment values that we chose, it
has been shown that shellsort in the worst case is O(N3/2). A detailed analysis
of shellsort and the impact of the increment sequence discussed in the next
section are presented in the third volume of Donald Knuth’s The Art of Com-
puter Programming (Addison-Wesley, 1998).
■ 3.3.2 The Effect of the Increment
The choice of the increment sequence can have a major effect on the order of
shellsort, and attempts at finding an optimal increment sequence have not be
successful. A number of different options have been considered, and their
results are presented here.