Shell Sort
Insertion sort with gaps n/2, n/4, ..., 1, so far-apart values move in big strides first.
Gap 4: compare index 0 (23) with index 4 (16), 4 apart. 23 > 16, so swap them and keep stepping back by 4.
What you will see
Elements a gap apart swap into order; the gap halves each round until it is plain insertion sort.
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
- ✓ comparison based
- × stable
- ✓ in place
- ✓ adaptive
- × online
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next, compare two runs.
Screen readers: Cells announce index, value and state (comparing, swapped, sorted); each step announces the comparison outcome and any move.
Reduced motion: Swaps become value crossfades with outline flashes; sorted-region growth is a static span change.
Before this
Related
Taught by the same lesson
More Sorts covers these too, in the same run.