• Home
• Contact

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

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$