Sortingintermediatecomparisonin-placegap-sequence

Shell Sort

Generalization of insertion sort that compares elements far apart, then narrows the gap.

How it works

Shell Sort is a generalisation of Insertion Sort that breaks its O(n²) worst case by first comparing and swapping elements that are far apart, then progressively narrowing the gap until a final pass with gap = 1 completes the sort. By the time the final insertion-sort pass runs, the array is nearly sorted, so very few shifts are required.

The algorithm's performance depends on the chosen gap sequence. The simple halving sequence (n/2, n/4, …, 1) used here gives O(n²) worst-case, but Hibbard's (2^k − 1), Sedgewick's, or Ciura's empirically optimised sequences can reduce the average case to O(n^{4/3}) or better. This flexibility makes Shell Sort one of the few sorting algorithms whose complexity is still an active research topic.

Shell Sort is in-place and requires no auxiliary arrays, making it attractive for memory-constrained environments. It is not stable — widely spaced swaps can change the relative order of equal elements. Its lack of recursion and minimal branching give it a very small code footprint, a property valued in embedded and firmware contexts.

Complexity

Best case

O(n log n)

Average case

O(n log² n)

Worst case

O(n²)

Space

O(1)

In-place

Visualizer

Generating steps…

Where it's used in the real world

uClibc / musl libc

Used as the default sort in some embedded C standard libraries

musl libc's qsort implementation historically used a variant of Shell Sort. The in-place, non-recursive nature keeps the compiled binary tiny — critical for embedded Linux systems where libc must fit in kilobytes of flash storage.

Early Unix kernels

Shell sort appeared in early Unix sort utilities due to simplicity

The original Unix sort utility used Shell Sort because it was compact enough to fit in the constrained address space of PDP-11 systems, required no dynamic memory allocation, and performed well enough on the small file sizes of the era.

Embedded systems (firmware)

Small code footprint, no recursion, O(1) extra space

Firmware targeting microcontrollers (ARM Cortex-M0, AVR) often cannot use stack-heavy recursive algorithms. Shell Sort's iterative structure, constant extra space, and single array make it a practical choice for sorting sensor tables, lookup tables, or configuration entries at startup.

Implementation

function shellSort(arr: number[]): number[] {
  const a = [...arr];
  const n = a.length;

  for (let gap = Math.floor(n / 2); gap >= 1; gap = Math.floor(gap / 2)) {
    for (let i = gap; i < n; i++) {
      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;
}

// Usage
console.log(shellSort([38, 27, 43, 3, 9, 82, 10, 55]));
// [3, 9, 10, 27, 38, 43, 55, 82]

Related algorithms

Insertion SortLive

Build a sorted array one element at a time by inserting into position.

O(n²)

Quick SortLive

Pick a pivot, partition around it, recursively sort partitions.

O(n log n)