Shell Sort

Run insertion sort over shrinking gaps so distant inversions disappear before the final adjacent pass.

Core idea

Apply insertion sort to elements separated by a large gap, then shrink the gap. Early passes move badly misplaced values long distances before the final gap-one cleanup.

Read the visualization

Dimmed bars are outside the current gap group. Within the active group, the key, comparisons, shifts, and insertion follow ordinary Insertion Sort at gap-sized distances.

Input

Reduce the gap and form a new set of interleaved subsequences.

1function shellSort(a: number[]): number[] {
const n = a.length;
for (let gap = n >> 1; gap > 0; gap >>= 1) {
  for (let start = 0; start < gap; start++) {
    for (let i = start + gap; i < n; i += gap) {
      const key = a[i];
      let j = i;
      while (j >= gap && a[j - gap] > key) {
        a[j] = a[j - gap];
        j -= gap;
      }
      a[j] = key;
    }
  }
}
return a;
17}

n10

gap5

group-

key7

a[j]7

shiftCount0

1 / 95

Complexity and tradeoffs

Time: Gap-dependent; common worst O(n^2). Space: O(1). In-place and often faster than insertion sort on medium arrays, but not stable.

Invariant: After finishing gap g, every subsequence formed by equal indices modulo g is sorted.

Where it fits

Shell Sort is compact, in-place, and practical for moderate arrays when a library sort is unavailable. Its performance depends strongly on the gap sequence and it is not stable.

Algorithm Visualizer

Shell Sort

Core idea

Read the visualization

Complexity and tradeoffs

Where it fits