Analysis of Algorithms : An Active Learning Approach

3.3 SHELLSORT 69

passes = lg N

while (passes ≥ 1) do

increment = 2passes - 1

for start = 1 to increment do

InsertionSort( list, N, start, increment )

end for

passes = passes - 1

end while

The variable increment gives the spacing between the elements of the

sublist. (In Fig. 3.1, the increments used are 8, 4, 2, and 1.) In the algorithm,

we start with an increment that is 1 less than the largest power of 2 that is

smaller than the size of the list. So, if our list has 1000 elements, our first incre-

ment will be 511. The increment also indicates the number of sublists that we

16 7 10 1 13 11 3814 4212 65915

14 421 511 3816 710 12 613 915

(a) Pass 1

(b) Pass 2

(c) Pass 3

(d) Pass 4

5 4 2 1 6 7 3 8 14 11 9 12 16 13 10 15

21345768911101214131615
■FIGURE 3.1
The four passes of
a shellsort