Shell sort

O(n^1.5)

Shell sort generalises insertion sort: instead of only comparing neighbours, it compares elements a fixed "gap" apart and runs an insertion sort on those, then halves the gap and repeats until the gap is 1. Moving items long distances early lets the final pass finish quickly. Its running time depends on the gap sequence — roughly O(n^1.5) for halving gaps.

Array
Edit the input and press Play

How it works

  1. Start with a large gap (here, half the array length).
  2. Run an insertion sort that compares elements that far apart.
  3. Halve the gap and repeat — the array gets steadily closer to sorted.
  4. Finish with gap = 1, a normal insertion sort over a nearly-sorted array.

Pseudocode

1shellSort(a):                       # O(n^1.5)2  for gap = n/2; gap > 0; gap /= 2:3    for i from gap to n-1:           # gapped insertion sort4      temp ← a[i]; j ← i5      while j ≥ gap and a[j-gap] > temp:6        a[j] ← a[j-gap]; j ← j - gap7      a[j] ← temp