Shell Sort
Insertion sort with gaps n/2, n/4, ..., 1, so far-apart values move in big strides first.
More Sorts: Shell sort with gaps 4, 2, 1
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
Before this
Taught by the same lesson
More Sorts covers these too, in the same run.