Speed
5×
Size
30
Phase
—
Current Gap
—
Gap Sequence
—
Gap
0
Comparisons
0
Shifts
0%
Sorted
Current Step
Legend
Gap group member
Key element (being inserted)
Comparing
Shifting right
Sorted / placed
Algorithm Info
Shell Sort
A generalization of insertion sort that allows the exchange of elements far apart. Uses a diminishing gap sequence. When gap = 1 it becomes ordinary insertion sort on an already nearly-sorted array.
Gap sequence (Knuth): 1, 4, 13, 40, 121… — i.e. 3h+1
| Best | O(n log n) |
| Average | O(n log² n) |
| Worst | O(n²) (Knuth) |
| Space | O(1) |
| Stable? | No |