Shell Sort

Insertion sort at shrinking gaps. Early passes move values long distances cheaply; the final gap-1 pass runs on nearly-sorted data where insertion sort shines.

Category: Sorting
Time complexity: O(n^1.3) (Depends on the gap sequence — Shell sort ranges from O(n²) with naive halving gaps down to O(n^4/3) or better with tuned sequences (Hibbard, Sedgewick). O(n^1.3) is the commonly cited figure for a well-chosen sequence.)
Space complexity: O(1)

Pseudocode

for gap in 4, 2, 1
  gapped insertion sort
  shift by gap steps
done

Reference implementation

for gap in (4, 2, 1):
    for i in range(gap, n):
        # gapped insertion sort
        while j &gt;= 0 and a[j] &gt; key:
            a[j + gap] = a[j]; j -= gap

Open the interactive Shell Sort visualisation →