Shell Sort

Shell Sort is an extension of Insertion Sort that improves its efficiency by comparing and moving elements that are farther apart. Named after its inventor, Donald Shell, this algorithm sorts elements in several passes with decreasing gap sizes, allowing the array to become nearly sorted before the final pass.

Definition

Shell Sort is a modified insertion sort that divides the list into several sublists. Each sublist consists of elements that are a fixed gap apart in the original list. By sorting these sublists, the algorithm gradually reduces disorder in the array. When the gap is eventually reduced to $1$, the list is almost sorted, and a final insertion sort quickly finishes the process.

Process

The algorithm works by comparing and exchanging elements that are not next to each other. Its procedure can be summarized as follows:

1. Divide the original array into several subarrays. Each subarray is formed by taking every $h$‑th element (where $h$ is the current gap).
2. Perform an insertion sort on each of these subarrays.
3. Reduce the gap and repeat the above steps until the gap becomes $1$.

This multi-pass approach allows the algorithm to move items closer to their final positions faster than a standard insertion sort.

Properties

Stability

Shell Sort is an unstable sorting algorithm. This means that the original relative order of elements with equal keys might not be preserved.

Time Complexity

The efficiency of Shell Sort depends largely on the gap sequence chosen. Although the best-case running time can be as efficient as $O(n)$, the average and worst-case performances vary with the gap sequence. Two classical gap sequences are:

• Proposition 1: If we choose the gap sequence

  $$H = \{ 2^k - 1 \mid k = 1,2,\ldots,\lfloor\log_2 n\rfloor \}$$

  (listed from largest to smallest), the time complexity of Shell Sort is $O(n^{3/2})$.

• Proposition 2: If we use the gap sequence

  $$H = \{ k = 2^p \cdot 3^q \mid p,q \in \mathbb{N},\, k \le n \}$$

  (again, in decreasing order), the time complexity becomes $O(n \log^2 n)$.

The reasoning behind these complexities involves several key theoretical results that capture how previous sorting passes help later ones.

Key Theoretical Concepts

1. Preservation of Sorted Sublists (Theorem 1):

   Once the array has been processed with insertion sort using a gap $h$, the elements at positions

   $$A_1, A_{1+h}, A_{1+2h}, \ldots$$

   are sorted. No matter how subsequent gap-based sorts (with different values of $h$) rearrange the array, this ordered structure in the $h$‑spaced subarrays remains intact. In simple terms, each pass “locks in” some order so that later passes have fewer disordered elements to handle.

2. A Number Theoretic Lemma (Lemma 2):

   A useful number theory result states that if two positive integers $a$ and $b$ are coprime, then the largest integer that cannot be written in the form

   $$ax + by \quad (x, y \in \mathbb{N})$$

   is

   $$ab - a - b.$$

   This lemma helps explain why combining the ordering from two different gap passes (especially when the gaps are relatively prime) maintains a beneficial structure in the array.

3. Combined Effect (Theorem 2):

   If consecutive gap values, say $h_{t+1}$ and $h_t$, are coprime, then after sorting with these gaps, performing an insertion sort with a smaller gap $h_{t-1}$ takes time proportional to

   $$O\left(\frac{n\, h_{t+1}\, h_t}{h_{t-1}}\right).$$

   Moreover, each element typically only moves about

   $O\left(\frac{h_{t+1}\, h_t}{h_{t-1}}\right)$

   positions during that pass. This result underscores how prior passes reduce the work needed in later passes.

The overall efficiency of Shell Sort can be understood by analyzing these theorems under different gap sequences. For example, with the gap sequence from Proposition 1, the work done by early passes (with larger gaps) and later passes (with smaller gaps) can be bounded in such a way that the total time complexity becomes $O(n^{3/2})$. Using the gap sequence from Proposition 2 further refines the analysis, leading to an overall complexity of $O(n \log^2 n)$.

Space Complexity

Shell Sort is an in-place algorithm, and its space complexity is $O(1)$ because it only requires a constant amount of extra storage.

Implementation

Below are two implementations of Shell Sort: one in C++ and another in Python.

template <typename T>
void shell_sort(T array[], int length) {
  int h = 1;
  while (h < length / 3) {
    h = 3 * h + 1;
  }
  while (h >= 1) {
    for (int i = h; i < length; i++) {
      for (int j = i; j >= h && array[j] < array[j - h]; j -= h) {
        std::swap(array[j], array[j - h]);
      }
    }
    h = h / 3;
  }
}

def shell_sort(array, length):
    h = 1
    while h < length / 3:
        h = int(3 * h + 1)
    while h >= 1:
        for i in range(h, length):
            j = i
            while j >= h and array[j] < array[j - h]:
                array[j], array[j - h] = array[j - h], array[j]
                j -= h
        h = int(h / 3)

Summary

Shell Sort improves Ordinary Insertion Sort by "pre-sorting" the array via a series of gap-based insertion sorts. This method dramatically reduces the number of movements needed when the gap is finally reduced to 1, allowing the algorithm to achieve good average performance. Understanding the underlying theory—how the sorted sublists are preserved and how clever gap sequences affect performance—can help in appreciating both the elegance and efficiency of this classic algorithm.