• Improves on insertion sort.
• Starts by comparing elements far apart, then elements less far apart,
  and finally comparing adjacent elements (effectively an insertion sort).
  By this stage the elements are sufficiently sorted that the running time
  of the final stage is much closer to O(N) than O(N²).

Shellsort, also known as the diminishing increment sort, is one of the oldest sorting algorithms, named after its inventor Donald. L. Shell (1959). It is fast, easy to understand and easy to implement. However, its complexity analysis is a little more sophisticated.

3 7 9 0 5 1 6 8 4 2 0 6 1 5 7 3 4 9 8 2

3 7 9 0 5 1 6
8 4 2 0 6 1 5
7 3 4 9 8 2

3 3 2 0 5 1 5
7 4 4 0 6 1 6
8 7 9 9 8 2

3 3 2
0 5 1
5 7 4
4 0 6
1 6 8
7 9 9
8 2

0 0 1
1 2 2
3 3 4
4 5 6
5 6 8
7 7 9
8 9

Actually, the data sequence is not arranged in a two-dimensional array, but held in a one-dimensional array that is indexed appropriately.

The algorithm uses an increment sequence to determine how far apart elements to be sorted are: h₁, h₂, ..., h_t with h₁ = 1

At first elements at distance h_t are sorted, then elements at distance h_t-1 are sorted, etc, until finally the array is sorted using insertion sort (distance h₁ = 1).

An array is said to be h_k-sorted if all elements spaced a distance h_k apart are sorted relative to each other.

Shellsort only works because an array that is h_k-sorted remains h_k-sorted when h_{k- 1}-sorted. This means that subsequent sorts with a smaller increment do not undo the work done by previous phases.

The correctness of the algorithm follows from the fact that in the last step (with h = 1) an ordinary Insertion Sort is performed on the whole array. Since data are presorted by the preceding steps
(h = 3, 7, 21, ...) only few Insertion Sort steps are sufficient.

• there is one additional loop (the outer loop) - each run processes one increment.
• the middle and the most inner loops are same as in insertion sort with gap = 1.

int j, p, gap;
comparable tmp;


for (gap = N/2; gap > 0; gap = gap/2)

  for ( p = gap; p < N ; p++)
  {
	tmp = a[p];
	for (j = p; j >= gap && tmp < a[j- gap]; j = j - gap)
	
		a[j] = a[j-gap];

	a[j] = tmp;
  }

}

What should the increment sequence be?
There are many choices for the increment sequence. Any sequence that begins at 1 and always increases will do, although some yield better performance than others:

1. Shell's original sequence: N/2 , N/4 , ..., 1 (repeatedly divide by 2);
2. Hibbard's increments: 1, 3, 7, ..., 2^k - 1 ;
3. Knuth's increments: 1, 4, 13, ..., (3^k - 1) / 2 ;
4. Sedgewick's increments: 1, 5, 19, 41, 109, ....
   Each term is of the form either 9 ·4^k - 9 ·2^k + 1 or 4^k - 3 ·2^k + 1.

A Shellsort's worst-case performance using Hibbard's increments is Θ(n ^3/2).
The average performance is thought to be about O(n^5/4)

The exact complexity of this algorithm is still being debated.

Experience shows that for mid-sized data (tens of thousands elements) the algorithm performs nearly as well if not better than the faster n log n sorts.