# Shellsort visualised: insertion sort with a gap sequence

> Interactive Shellsort: generalised insertion sort that first sorts far-apart pairs and shrinks the gap to 1. Worst case O(n^2) with the standard gap sequence.

Address: https://marckimmel.de/en/informatik/sortieralgorithmen/shell-sort
Deutsche Fassung: https://marckimmel.de/informatik/sortieralgorithmen/shell-sort.md

Generalised Insertion Sort: first sorts far-apart pairs, then progressively closer ones.

Shellsort is a generalisation of Insertion Sort. Instead of comparing only direct neighbours, it sorts elements that are a larger gap apart. Each phase reduces the gap until it reaches 1, where the final pass behaves like a regular Insertion Sort. The pre-sorting of far-apart pairs moves elements quickly across long distances toward their target. The gap sequence (n/2, n/4, …, 1 in the simplest variant) heavily impacts runtime: the simple sequence yields O(n²) worst case, while better sequences like Sedgewick or Ciura drop the worst case to O(n^(4/3)) or better. Shellsort runs in-place with O(1) extra memory but is not stable.

Useful on medium-sized arrays when a simple in-place algorithm is enough and no O(n log n) worst-case guarantee is needed. Occasionally found in embedded code or as a subroutine in more complex algorithms.

## Related

- [Sorting Algorithms](https://marckimmel.de/en/informatik/sortieralgorithmen.md)