Shellsort
Generalised Insertion Sort: first sorts far-apart pairs, then progressively closer ones.
- Comparisons 0
- Swaps 0
- sorted indices 0
- compare
- swap
- sorted
Pseudocode
1 for gap = n/2 down to 1, gap /= 2
2 for i from gap to n - 1
3 temp = a[i]; j = i
4 while j >= gap and a[j - gap] > temp
5 a[j] = a[j - gap]; j -= gap
6 a[j] = temp
Step log
- 1Start.
How it works, runtime and memory
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.
Complexity
- Best case
- O(n log n)
- Average case
- O(n4/3)
- Worst case
- O(n2)
- Extra space
- O(1)
When to use it
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.