# shell sort sequence implementation in C++

I am reading about shell sort in Algorithms in C++ by Robert Sedwick.

Here outer loop to change the increments leads to this compact shellsort implementation, which uses the increment sequence 1 4 13 40 121 364 1093 3280 9841 . . . .

```template <class Item>
void shellsort(Item a[], int l, int r)
{
int h;
for (h = 1; h <= (r - l) / 9; h = 3 * h + 1);
for (; h > 0; h = h / 3)
{
for (int i = l + h; i <= r; i++)
{
int j = i; Item v = a[i];
while (j >= l + h && v < a[j - h])
{
a[j] = a[j - h]; j -= h;
}
a[j] = v;
}
}
}
```

My question under what basis author is checking for condition h <= (r-l)/9, and why author is dividing by 9.

The loop:

```for (h = 1; h <= (r - l) / 9; h = 3 * h + 1);
```

calculates the initial value of h. This value must be smaller than the range it will be used in:

```h <= (r - l)
```

Everytime this condition passes, h gets updated to 3 * h + 1, which means that even though h is smaller than (r-l), the updated value might be larger. To prevent this, we could check if the next value of h would surpass the largest index:

```(h * 3) + 1 <= (r - l)
```

This will make sure h is smaller than range of the array.

For example: say we have an array of size 42, which means indices go from 0 to 41. Using the condition as described above:

```h = 1, is (3 * 1 + 1) <= (41 - 0) ? yes! -> update h to 4
h = 4, is (3 * 4 + 1) <= (41 - 0) ? yes! -> update h to 13
h = 13, is (3 * 13 + 1) <= (41 - 0) ? yes! -> update h to 40
h = 40, is (3 * 40 + 1) <= (41 - 0) ? no! => h will begin at 40
```

This means our initial h is 40, because h is only marginally smaller than the range of the array, very little work will be done, the algorithm will only check the following:

1. Does array[40] needs to be swapped with array[0] ?
2. Does array[41] needs to be swapped with array[1] ?

This is a bit useless, the first iteration only performs two checks. A smaller initial value of h means more work will get done in the first iteration.

Using:

```h <= (r - l) / 9
```

ensures the initial value of h to be sufficiently small to allow the first iteration to do useful work. As an extra advantage, it also looks cleaner than the previous condition.

You could replace 9 by any value greater than 3. Why greater than 3? To ensure (h * 3) + 1 <= (r - l) is still true!

But do remember to not make the initial h too small: Shell Sort is based on Insertion Sort, which only performs well on small or nearly sorted arrays. Personally, I would not exceed h <= (r - l) / 15.