Interactive demo
Shell Sort Visualization
Shell sort, published by Donald Shell in 1959, improves insertion sort: elements first jump over large gaps, so they quickly get close to their place. The final pass is a normal insertion sort on a nearly sorted array.
The pass with gap 4 moves elements far quickly, so the final insertion sort with gap 1 has little left to do.
Playback
- Comparisons
- 0
- Writes
- 0
Array
Legend
- Element
- Chain of the current gap
- Element being inserted
- Compared element
- Final position
Runtime and properties
Best case
O(n log n)
Sorted input: each gap pass only needs one comparison per element.
Average case
≈ O(n1.25)
Measured in experiments for Knuth's gaps; no exact bound has been proven.
Worst case
O(n1.5)
With Knuth's gaps 1, 4, 13, 40 … the worst case is n1.5.
Extra memory
O(1)
Like insertion sort, only the element being inserted is held aside.
Stable
No
Jumps over large gaps can pass equal elements.
In-place
Yes
Elements are shifted within the array.
n is the number of elements. O(n log n) is the best a sorting algorithm based on comparisons can achieve.
Compared with the other sorting algorithms
| Algorithm | Best case | Average case | Worst case | Extra memory | Stable | In-place |
|---|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | No | Yes |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Shell sort this page | O(n log n) | ≈ O(n1.25) | O(n1.5) | O(1) | No | Yes |
| Tree sort | O(n log n) | O(n log n) | O(n²) | O(n) | Yes | No |
| Tournament sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Yes |
| Smoothsort | O(n) | O(n log n) | O(n log n) | O(1) | No | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Patience sort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Block sort | O(n) | O(n log n) | O(n log n) | O(1) | Yes | Yes |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Yes |
| Introsort | O(n log n) | O(n log n) | O(n log n) | O(log n) | No | Yes |
| Fluxsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Crumsort | O(n) | O(n log n) | O(n log n) | O(log n) | No | Yes |
1. Gaps
The gaps come from Donald Knuth's sequence 1, 4, 13, 40 …, largest first. With 11 elements these are 4 and 1.
2. Insertion sort per chain
For a gap of 4, the elements at positions 0, 4, 8 form a chain, as do 1, 5, 9 and so on. Each chain is sorted with insertion sort, so an element moves 4 places per shift.
3. The last gap is 1
The final pass is a normal insertion sort. Because the large gaps already moved most elements close to their place, it only needs a few shifts.