Shell Sort — Mathematical Foundations and Complexity Theory¶

Definition (Shell Sort).
  Input:  array A[0..n-1] of comparable elements.
  Output: A[0..n-1] permuted such that A[0] <= A[1] <= ... <= A[n-1].

  Parameter: a gap sequence G = (g_1, g_2, ..., g_t)
             with g_1 > g_2 > ... > g_t = 1 and g_t = 1.

  Procedure:
    for k = 1 to t:
        H-SORT(A, g_k)

  where H-SORT(A, h) is gapped insertion sort:
    for i = h to n-1:
        x = A[i]
        j = i
        while j >= h and A[j - h] > x:
            A[j] = A[j - h]
            j = j - h
        A[j] = x

Claim. After Shell Sort terminates, A is non-decreasing.

Loop Invariant (outer). At the start of iteration k of the outer loop,
                       A is h-sorted for h = g_{k-1} (vacuously for k = 1).

Base case (k = 1). No constraint required.

Inductive step. Assume A is h-sorted with h = g_{k-1}. We show that after
H-SORT(A, g_k), A is h-sorted for h = g_k.

H-SORT(A, g_k) is insertion sort on each of the g_k subsequences of stride g_k.
Insertion sort correctness: each subsequence becomes sorted, i.e.,
A[i] <= A[i + g_k] for all i with i + g_k < n. Hence A is g_k-sorted. QED inner.

Termination. The outer loop runs exactly t iterations (finite).
            Each H-SORT terminates because:
              outer for i: bounded by n - h iterations;
              inner while: j strictly decreases by h, bounded by 0.

Postcondition. After iteration t, A is g_t-sorted = 1-sorted, i.e.,
              A[i] <= A[i + 1] for every i, so A is non-decreasing. QED.

Theorem (Knuth, TAOCP Vol. 3, Theorem 5.2.1.K).
  If A is h-sorted and we apply k-sort to A, then A becomes k-sorted
  AND remains h-sorted.

Proof sketch. Consider any pair (i, i + h) with i + h < n. Before k-sort:
A[i] <= A[i + h] by hypothesis. k-sort moves elements only along stride-k
subsequences. We show the (i, i + h) ordering is preserved.

Both A[i] and A[i + h] participate in k-sort. Let A'[i] and A'[i + h]
denote their post k-sort positions/values. By a case analysis on whether
i mod k == (i + h) mod k:

  Case 1: same residue. Both stay on the same subsequence; insertion sort
          preserves relative order along that subsequence, but a stride-h
          subset of a stride-k sorted subsequence is still sorted. Hence
          A'[i] <= A'[i + h].

  Case 2: different residues. The two are on disjoint subsequences.
          The k-sort permutes A[i] only among its k-residue class.
          A general argument (see Pratt, 1971, Lemma 3.1) shows that the
          h-sortedness invariant is preserved across all residue classes. QED.

Theorem. Shell's original sequence yields worst-case Theta(n^2).

Proof outline. Construct adversary: place small values at even indices,
large values at odd indices. All h_i for h_i > 1 are even, so each pass
sorts even and odd subsequences independently. The final 1-sort merges
them at cost Theta(n^2). QED.

Theorem (Papernov & Stasevich, 1965).
  Hibbard's sequence yields worst-case O(n^(3/2)).

Proof sketch. Pairwise coprime gaps mean each pass mixes residues. A bound
on inversions remaining after pass k:
  inv_k <= n^2 / (g_k · g_{k+1})
After all passes, total work is Sum_k inv_k = O(n^(3/2)). QED.

Theorem (Sedgewick, 1986).
  Sequence g_i = 9 · 4^i - 9 · 2^i + 1 interleaved with 4^i - 3 · 2^i + 1
  yields worst-case O(n^(4/3)).

Proof outline. A more careful potential argument using a 2-D embedding of
inversions: each gap pair (g_i, g_{i+1}) reduces inversions by a factor
proportional to (g_{i+1})^(1/3). Summing gives O(n^(4/3)). Full proof in
Sedgewick (1986). QED.

Empirical: ~O(n^(5/4)). No tight proven worst-case bound below O(n^(3/2)).

Theorem (Pratt, 1971).
  Shell Sort using the gap sequence {2^a * 3^b : 2^a * 3^b <= n} runs in
  Theta(n log^2 n) time in the worst case.

Proof sketch.

Step 1: Count gaps.
  Number of (a, b) with 2^a * 3^b <= n:
    For each a in [0, log_2 n], b ranges over [0, log_3 (n / 2^a)].
    Total = Sum_{a=0}^{log n} log_3 (n / 2^a) = O(log^2 n).
  So |G| = O(log^2 n).

Step 2: Each pass costs O(n).
  Claim: once A is 2-sorted AND 3-sorted, applying any (2^a * 3^b)-sort
  costs O(n).

  Reason: a 2- and 3-sorted array has the property that for every i,
  A[i] <= A[i + 2] and A[i] <= A[i + 3]. By a covering argument over
  positions reachable as 2x + 3y combinations (Chicken McNugget Theorem),
  the array is g-sorted for every g >= 2. In particular, A[i] is at most
  O(1) positions away from its target during the g-sort pass.

  Each H-SORT pass at gap g costs O(n) when arrays are 2- and 3-sorted.

Step 3: Combine.
  Total work = (#passes) * (work per pass) = O(log^2 n) * O(n) = O(n log^2 n).

Step 4: Lower bound. The matching Omega(n log^2 n) lower bound for this
specific sequence uses adversarial inputs that force the algorithm to
process log^2 n meaningful inversions. QED.

Question. What is the best possible worst-case complexity of Shell Sort,
          minimized over all gap sequences?

Known:
  - Information theoretic lower bound for any comparison sort: Omega(n log n).
  - Shell Sort with any gap sequence is Omega(n log n) in the comparison model.
  - Pratt achieves O(n log^2 n).
  - No proven gap sequence achieves O(n log n).
  - No proven lower bound above Omega(n log n) for Shell Sort.

Conjecture (open since 1971).
  Either there exists a gap sequence yielding worst-case O(n log n)
  (matching the information-theoretic bound), or there is a Shell-Sort-specific
  lower bound strictly above Omega(n log n).

Both directions remain unsettled despite 50+ years of research.

Comparison Sort Lower Bound:
  Any comparison-based sort on n elements requires at least
  log_2(n!) ≈ n log_2 n - n / ln(2) comparisons in the worst case.

  Proof. Decision tree of comparison sorts has n! leaves (one per
  permutation). Tree height >= log_2(n!). Stirling: log_2(n!) = Theta(n log n). QED.