AlgoScope

Shell Sort

Insertion sort with gaps n/2, n/4, ..., 1, so far-apart values move in big strides first.

Sorting, algorithm, intermediate
Compare 23 and 16, 4 apart: swap.16051422832344515697ij23 > 16
Compare 23 and 16, 4 apart: swap.16051422832344515697ij23 > 16

More Sorts: Shell sort with gaps 4, 2, 1

Decision, step 2 of 29

Gap 4: compare index 0 (23) with index 4 (16), 4 apart. 23 > 16, so swap them and keep stepping back by 4.

Cost

Best
O(n log n)
Average
depends on gap sequence
Worst
O(n^2)
Space
O(1)

Worst case O(n^(3/2)) with Knuth gaps. Exact average unknown for most sequences.

Properties

  • Yes: Comparison based
  • No: Stable
  • Yes: In place
  • Yes: Adaptive
  • No: Online

Taught by the same lesson

More Sorts covers these too, in the same run.