programming / C++ / sailing / nerd stuff
Algorithm: Shell Sort

## Description

Sorting of h parts in distance of the elements of h. Merging the parts for descending order of h values with insertion sort. This means the elements gets moved over a greater distance. Typical: $h(k+1) = 3 * h(k) + 1$

• not stable

## Algorithm

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16  int h = 1; while (h <= array.count()) { h = 3*h+1; } while (h > 0) { h = h / 3; for (int i = (h-1); i < array.count(); ++i) { int j = i; while ((j > h-1) && (array[j] < array[j-h-1])) { array.swap( j-h-1, j ); j = j - h - 1; } } }

## Analysis

Asymptotic complexity depends on h:

For $h(k+1) = 3 * h(k) + 1$:

$M_{avg} = 1.29 * n^1.28$

$C_{avg} = O( n^3/2 )$

For $h(k+1) = 2 * h(k)$:

$M_{avg} = O( n^3/2 )$

$C_{avg} = O(n^3/2)$

For $h = 2^p * 3^q {..., 16, 12, 9, 8, 6, 4, 3, 2, 1}$:

$M_{avg} = O(n * log^2(n))$

For $h = floor(n * \alpha), floor(floor(n * \alpha) * \alpha), ..., 1$:

$M_{avg} = 1.75 * n^1.19$