# 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.

## Answers

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:

- Does array[40] needs to be swapped with array[0] ?
- 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.