Shell Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Shell Sort

Insertion Sort, but on widely-spaced sub-arrays first. The gap shrinks each pass until a final gap of 1 finishes a nearly-sorted array fast.

How it works

Shell Sort, invented by Donald Shell in 1959, was one of the first sub-quadratic sorts. It chooses a sequence of gaps g₁ > g₂ > ... > 1 and runs gapped insertion sorts in sequence.

1. Pick a gap sequence (e.g., n/2, n/4, ..., 1, or Ciura's tuned [701, 301, 132, 57, 23, 10, 4, 1]).
2. For each gap g, do an insertion sort where the "neighbor" of i is i − g.
3. Continue with smaller gaps. The final pass with g = 1 is plain insertion sort, but the array is now almost sorted, so it runs close to linear.

Time complexity depends heavily on the gap sequence. With Ciura's sequence, empirical performance is near O(n log² n); theoretical worst-case bounds reach O(n^{4/3}) with Sedgewick gaps.

Complexity

Interactive visualization

Pseudocode

procedure shellSort(A):
  gaps ← [701, 301, 132, 57, 23, 10, 4, 1]
  for gap in gaps where gap < n:
    for i from gap to n − 1:
      temp ← A[i]; j ← i
      while j ≥ gap and A[j − gap] > temp:
        A[j] ← A[j − gap]; j ← j − gap
      A[j] ← temp

JavaScript implementation

function shellSort(arr) {
  const gaps = [701, 301, 132, 57, 23, 10, 4, 1];
  for (const gap of gaps) {
    if (gap >= arr.length) continue;
    for (let i = gap; i < arr.length; i++) {
      const temp = arr[i];
      let j = i;
      while (j >= gap && arr[j - gap] > temp) {
        arr[j] = arr[j - gap]; j -= gap;
      }
      arr[j] = temp;
    }
  }
  return arr;
}

Pros and cons

When to use it

• Embedded systems where binary size matters and you need better than O(n²).
• Medium arrays (n < 10⁵) when simplicity is valued.
• Avoiding recursion for stack-limited environments.