Home/Sorting/Shell sort
Search algorithmsCTRL K

Shell sort

· insertion sort over gapped subsequences
/sorting/shell-sort
COMPARISONS
0
so far
SHIFTS
0
elements moved right by a gap
GAP
12
distance inside a subsequence
GAP PASSES
1
n/2, n/4, …, 1
KEY
—
the lifted value
lifted outcomparingmovedin place
n = 24 · seed 7 · 320 steps
step 0 / 319
Size24
shell_sort.ts
1
function shellSort(array: number[]) {
2
  for (let gap = Math.floor(array.length / 2); gap > 0; gap = Math.floor(gap / 2)) {
3
    for (let i = gap; i < array.length; i++) {
4
      const key = array[i];
5
      let j = i;
6
      while (j >= gap && array[j - gap] > key) {
7
        array[j] = array[j - gap];
8
        j -= gap;
9
      }
10
      array[j] = key;
11
    }
12
  }
13
}
CURRENT STEP
line 2

Gap 12: insertion sort every subsequence of elements 12 apart.

// how it works

Understanding Shell sort

shell sort · coarse passes first, so the last pass has almost nothing to do
01

The idea

Shell sort runs insertion sort on subsequences of elements a fixed gap apart, then shrinks the gap and repeats, ending with gap 1, which is plain insertion sort. Each coarse pass moves elements long distances cheaply, so by the final pass every element is close to its place and insertion sort runs near its linear best case.

The gap sequence decides the running time. Halving, as here, gives O(n²) in the worst case but O(n^1.5) typically; sequences like Ciura's 1, 4, 10, 23, 57, 132, … do measurably better, and the true complexity of the best sequence is still an open problem.

02

The four stages

1
pick a gapn/2, then halve it each pass
2
lifteach element in turn, from index gap on
3
shiftlarger elements gap places right
4
placethe key in its gapped slot
03

Complexity

best
O(n log n)already sorted: every pass is linear
average
O(n^1.3)halving gaps; better sequences do better
worst
O(n²)halving gaps on a crafted input
space
O(1)in place
04

Versus its siblings

COMPARISONS AT N = 1 000 · RANDOM INPUT
bubble
499,500
insertion
250,000
shell
24,000
quick
13,900
merge
8,700
same random input for every algorithm
05

Pseudocode

SHELLSORT(array)
  for gap ← ⌊n/2⌋, ⌊n/4⌋, …, 1
    for i ← gap to n − 1
      key ← array[i]; j ← i
      while j ≥ gap and array[j − gap] > key: array[j] ← array[j − gap]; j ← j − gap
      array[j] ← key
06

When to use

Embedded and kernel code where recursion and extra memory are unwelcome: uClibc's qsort and parts of the Linux kernel use it.
Medium arrays, a few thousand elements, where it is within a small factor of quick sort with far simpler code.
07

Pitfalls

Not stable: elements jump over each other across gaps.
Gap sequences with common factors (8, 4, 2, 1) waste passes; the elements never mix between subsequences until the end.
Its running time is hard to predict; if you need a guarantee, use heap sort or merge sort.
08

History

Donald Shell published it in 1959, the first sort to break the O(n²) barrier in practice. The analysis has occupied Knuth, Pratt, Sedgewick and others for sixty years; Pratt proved O(n log² n) for the 2ᵖ3ᵠ sequence in 1971, and the gap sequence question remains open.

Back to Sorting