Shell sort algorithm

Operation performing:

Comparisons done:

Elements moved:

Legend:
28	- elements of the original array
13	- sub-array currently being sorted
13	- each shade of fuscia represents a sort of a given sub-array
20	- yet untached elements

The shell sort algorithm, named after its inventor Donald Shell, works as follows.

First we select a sequence of integer steps (e.g. 1, 4, 13, 40, 121, ... or 1, 8, 23, 77, 281, 1073, ...)
Then we determine the largest element h of the sequence such that size of array divided by that element is about 9 (or the size of initial sub-arrays we would like to sort).
Now the algorithm begins:
1. We select a sub-array of the given array such that the index of the first element of the sub-array is zero, the index of the second element is h, index of the third element is 2*h, etc.
2. We sort the selected sub-array using the insertion sort
3. We select another sub-array such that the first element has index 1, second has index 1+h, third 1+2*h, etc
4. We sort this sub-array.
5. We select the next sub-array, etc..
6. When all possible sub-arrays with the given step h are selected and sorted. We set the value of the step h equal to the previous element in the sequence. (For example, if we use the first sequence and the first step was 40, then the next step will be 13.)
7. Keep repeating the algorithm until h=1 and the corresponding sub-array (which is actually the whole array) is sorted.

Q: How do we decide what increment sequence to use?

So far no provably best sequence has been found. Many sequences have been studied in literature, and some have been found that work well in practice. In practice, we generally use sequences that decrease roughly geometrically, so the number of increments is logarithmic in the size of the file. The practical effect of finding a good increment sequence is limited to perhaps a 25% speedup. Here are several increment sequences:

1 4 13 40 121 364 1093 3280 9841 ... (a_i = 3*a_i-1+1) was recommended by Knuth in 1969 and leads to a relatively efficient sort. Many sequences lead to a more efficient sort but it is difficult to beat this one by more than 20%.
Property: Shell sort does less than O(N^3/2) comparisons for this increment sequence.
1 8 23 77 281 1073 4193 ... (a_i = 4ⁱ⁺¹+3*2ⁱ+1) - this sequence has probably the fastest worst-case behavior.
Property: Shell sort does less than O(N^4/3) comparisons for this increment sequence.
1 2 4 8 16 32 64 128 256 512 ... (a_i = 2^i-1) - bad increment sequence originally proposed by Shell (the inventor of the algorithm).

1 2 3 4 6 9 8 12 18 27 16 24 36 54 81 ... - the "triangle increment" sequence

						1
					2		3
				4		6		9
			8		12		18		27
		16		24		36		54		81
	32		48		72		108		162		243
64		96		144		216		324		486		729

Property: Shell sort does less than O(N*(log N)²) comparisons for this increment sequence.

Hibbard;s sequence: 1 3 7 15 31 ... (a_i = 2ⁱ-1)
Property: Shell sort does less than O(N^3/2) comparisons for this increment sequence.
{ αⁱ }, where x is the largest integer less than or equal to x. Assignment: experimentally determine the value of α that leads to the lowest running time for random arrays.