Shellsort

in progressThis lesson is still being built - content, demos, and checkpoints may change before release.

Shellsort

Loading interactive demo…

Shellsort runs insertion sort on bars a fixed gap apart, then shrinks the gap and repeats until a final gap of 1. Large gaps move bars long distances cheaply; the last pass is an ordinary insertion sort on nearly ordered data. Take the tour, or press and explore. Legend:

The panel beside the stage is the real ShellSort class from the published library executing in your browser, with the current line highlighted.

The bar being placed within its chain (always the brightest bar).
The bar one gap to its left, the one it is checked or swapped against. The bracket spans the pair.
Bars of the same chain already in order.
A chain: bars sharing a tint sit the same number of slots apart (the same remainder when their slot is divided by the gap) and are sorted together during a pass.
Every bar, once the whole array is sorted.

The gaps come from Ciura's sequence (1, 4, 10, 23, 57, 132, 301, 701), the best known set for the average case, found by experiment rather than proof. Watch the gap readout shrink and the swap count barely move during the last pass.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

A pass at gap $h$ is an insertion sort of $h$ interleaved chains, each about $n/h$ long, and its cost depends on how disordered those chains still are. The trick is that a pass at gap $h$ keeps the array sorted for every earlier, larger gap, so each new pass starts on data the previous ones have already tamed. How much that helps depends entirely on the gap sequence:

\text{halving (Shell)}: O(n^2) \qquad \text{Hibbard}: O(n^{3/2}) \qquad \text{Sedgewick}: O(n^{4/3})

Ciura's gaps, the ones the class uses, are the best known on average, but they were found by experiment and their exact worst case is an open problem: $O(n^{4/3})$ is the usual estimate. The best case is a sorted input, where every pass makes about $n$ comparisons and no swaps: $O(n \log n)$ over the roughly $\log n$ passes. Shellsort is in place, using $O(1)$ extra space, and it is not stable: a long hop can carry a bar past an equal one.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

The gap sequence is a plain field, gaps, listed largest first, and if (gap >= n) continue picks out the ones that fit: 16 bars run gaps 10, 4 and 1, while 4 bars run only 1.
Each pass is the exchange form of insertion sort: j -= gap is the leftward scan, and every out-of-order pair is swapped, so each hop is visible on the stage. A shifting version that holds the key in a variable writes fewer slots but tells the same story.
Nothing special happens at gap 1. The same loop runs with a stride of one, and that pass is insertion sort, line for line, on an array the earlier passes already nearly sorted.
a[j - gap] <= a[j] stops the scan as soon as the chain is in order to the left, the same early exit that makes insertion sort linear on sorted input.
Ciura's list ends at 701, which serves arrays up to a few thousand elements; larger inputs would extend it by a factor of about 2.25 per gap.

Donald Shell published the method in a three-page 1959 paper in Communications of the ACM: run insertion sort on elements a fixed gap apart, shrink the gap, and finish with a plain insertion sort on data that is by then nearly ordered. It was the first practical sort to break the quadratic barrier, and the question it opened, which gap sequence is best, is still not fully answered.

1959Donald Shell - Publishes 'A High-Speed Sorting Procedure' in Communications of the ACM, sorting at diminishing gaps that halve each pass.source
1963Thomas Hibbard - Proposes gaps one less than a power of two (1, 3, 7, 15, ...), a sequence that runs in Θ(n^(3/2)) time, well below quadratic.source
1971Vaughan Pratt - His Stanford doctoral work, later published as 'Shellsort and Sorting Networks', shows that gaps of the form 2^p 3^q run in Θ(n log² n) time.source
1986Robert Sedgewick - 'A New Upper Bound for Shellsort' gives a gap sequence with a proven O(n^(4/3)) running time.source
2001Marcin Ciura - 'Best Increments for the Average Case of Shellsort' finds the sequence 1, 4, 10, 23, 57, 132, 301, 701 by experiment; this lesson's class uses it.source

Used today

Embedded C libraries - uClibc, a C library for embedded Linux, implements its qsort with a Shellsort: tiny code, no recursion, no extra memory.
The bzip2 compressor - bzip2 sorts short subarrays with Shellsort during its block-sorting stage.
Small or nearly sorted inputs - Systems code reaches for it where the array is small and a simple, in-place, non-recursive sort beats the overhead of a fancier one.

n16

gap: 10
comparisons: 0
swaps: 0

shell-sort.ts

import type { Tracer } from "../trace";import type { SortAlgorithm } from "./sort-algorithm";/** * Shellsort: insertion sort over elements a fixed gap apart, repeated * with shrinking gaps (Ciura's sequence) so far-apart elements travel * long distances in one hop. Each pass swaps out-of-order pairs one gap * apart; the final gap-1 pass is a plain insertion sort on nearly * ordered data. * * Time: O(n^(4/3)) or better in practice with Ciura's gaps; the exact * worst case is open. Space: O(1) extra. */export class ShellSort implements SortAlgorithm {  readonly name = "shell-sort";  readonly gaps = [701, 301, 132, 57, 23, 10, 4, 1];  constructor(private readonly tracer?: Tracer) {}  sort(input: readonly number[]): number[] {    const a = [...input];    const array = [...input];    const n = a.length;    const n = array.length;    for (const gap of this.gaps) {      if (gap >= n) continue;      // ▸ start a pass: insertion-sort every chain of bars this gap apart      this.tracer?.emit("gap", { gap, array: [...a] });      this.tracer?.emit("gap", { gap, array: [...array] });      for (let i = gap; i < n; i++) {      for (let position = gap; position < n; position++) {        for (let j = i; j >= gap; j -= gap) {        for (let cursor = position; cursor >= gap; cursor -= gap) {          // ▸ look at the bar one gap to the left of the cursor          this.tracer?.emit("compare", { gap, i, j, array: [...a] });          this.tracer?.emit("compare", { gap, position, cursor, array: [...array] });          if (a[j - gap]! <= a[j]!) break;          if (array[cursor - gap]! <= array[cursor]!) break;          // ▸ it is bigger, so swap the pair and step the cursor back a gap          this.tracer?.emit("swap", { gap, i, j, array: [...a] });          this.tracer?.emit("swap", { gap, position, cursor, array: [...array] });          const held = a[j]!;          const held = array[cursor]!;          a[j] = a[j - gap]!;          array[cursor] = array[cursor - gap]!;          a[j - gap] = held;          array[cursor - gap] = held;        }      }    }    return a;    return array;  }}

The array before sorting. Shellsort will insertion-sort it at shrinking gaps, the biggest gap first.

import type { Tracer } from "../trace";import type { SortAlgorithm } from "./sort-algorithm";/** * Shellsort: insertion sort over elements a fixed gap apart, repeated * with shrinking gaps (Ciura's sequence) so far-apart elements travel * long distances in one hop. Each pass swaps out-of-order pairs one gap * apart; the final gap-1 pass is a plain insertion sort on nearly * ordered data. * * Time: O(n^(4/3)) or better in practice with Ciura's gaps; the exact * worst case is open. Space: O(1) extra. */export class ShellSort implements SortAlgorithm { readonly name = "shell-sort"; readonly gaps = [701, 301, 132, 57, 23, 10, 4, 1]; constructor(private readonly tracer?: Tracer) {} sort(input: readonly number[]): number[] { const a = [...input]; const array = [...input]; const n = a.length; const n = array.length; for (const gap of this.gaps) { if (gap >= n) continue; // ▸ start a pass: insertion-sort every chain of bars this gap apart this.tracer?.emit("gap", { gap, array: [...a] }); this.tracer?.emit("gap", { gap, array: [...array] }); for (let i = gap; i < n; i++) { for (let position = gap; position < n; position++) { for (let j = i; j >= gap; j -= gap) { for (let cursor = position; cursor >= gap; cursor -= gap) { // ▸ look at the bar one gap to the left of the cursor this.tracer?.emit("compare", { gap, i, j, array: [...a] }); this.tracer?.emit("compare", { gap, position, cursor, array: [...array] }); if (a[j - gap]! <= a[j]!) break; if (array[cursor - gap]! <= array[cursor]!) break; // ▸ it is bigger, so swap the pair and step the cursor back a gap this.tracer?.emit("swap", { gap, i, j, array: [...a] }); this.tracer?.emit("swap", { gap, position, cursor, array: [...array] }); const held = a[j]!; const held = array[cursor]!; a[j] = a[j - gap]!; array[cursor] = array[cursor - gap]!; a[j - gap] = held; array[cursor - gap] = held; } } } return a; return array; }}