SortingSorting

Shell Sort

Insertion sort over elements h apart with a shrinking gap sequence, finishing with a plain insertion sort.

Learn Shell Sort →
29
0
10
1
14
2
37
3
13
4
5
5
42
6
21
7
1/51Start with gap = 4. Shell sort runs insertion sort on elements gap apart, so far-away elements move in one hop instead of many adjacent swaps.
Key being insertedElement gap positions leftShifted right by gapSorted
PseudocodeLearn Shell Sort →
1gap = n // 2
2while gap > 0:
3  for i in gap .. n-1:
4    key = a[i]; j = i
5    while j >= gap and a[j-gap] > key:
6      a[j] = a[j-gap]; j -= gap
7    a[j] = key
8  gap = gap // 2
Variables
gap4
Complexity
best O(n log n)
avg O(n^1.25)–O(n^1.5)
worst O(n^1.5)
space O(1)
Speed