Shellsort

Shellsort sorts an array of items according to sequence $h_1, h_2, \ldots, h_k$ which specify the distance between element $A[i]$ and $A[i+h_k]$ that should be sorted. This distance will then be decremented until the last phase.

Characteristics

A $h_k$-sorted array that is then $h_k-1$-sorted will remain $h_k$-sorted.

Analysis

The running time is highly influenced by the gap sequence.
It will result in $\Theta(N^2)$ in the worst case by using the Shell sequence $\lfloor \frac{N}{2^k} \rfloor$.
It will result in $\Theta(N^{\frac{3}{2}})$ in the worst case by using the Hibbard sequence $2^k - 1$.
It will result in $O(N^{\frac{4}{3}})$ in the worst case by using the Sedgewick sequence:

$$ \begin{cases} 9 \cdot 4^k - 9 \cdot 2^k + 1 & \quad \text{if } k \text{ is even}\\ 4^k - 3 \cdot 2^k + 1 & \quad \text{if } k \text{ is odd} \end{cases} $$

Implementation

Note: This sorting algorithm sorts items in ascending order.

void Shellsort(ElementType A[], int N) {
  int j;

  ElementType Tmp;
  for (int Increment = N / 2; Increment > 0; Increment /= 2)
    for (int i = Increment; i < N; i++) {
      Tmp = A[i];
      for (j = i; j >= Increment; j -= Increment)
        if (Tmp < A[j - Increment])
          A[j] = A[j - Increment];
        else
          break;
      A[j] = Tmp;
    }
}