Shell Sort
- Ω( n log n )
- Θ( n4/3 )
- O( n2 )
- space O( 1 )
Array
Comparator strip
Index down, time to the right
- Comparisons count only element-against-element checks; loop and index checks are never counted.
- Reads and writes include reads and writes to helper buffers (merge, counting, radix, bucket and tim sort).
- A swap counts once, as a swap. It is never also counted as a read or a write.
- Real time is the average time of the counted sort on this device over repeated runs, measured once before playback and independent of animation speed. Visual time is the time spent animating, excluding pauses.
How shell sort works
Shell sort generalises insertion sort to elements that are far apart. It insertion-sorts the array several times, each time with a smaller gap between the elements it compares, and finishes with gap 1, a plain insertion sort on an almost sorted array.
Read more
The gaps here are Ciura's empirically found sequence. The exact average running time for such sequences is an open problem, so the average listed is an estimate. Shell sort needs no extra memory and is fast for medium-sized arrays.
| Best time | Ω( n log n ) | good |
|---|---|---|
| Average time | Θ( n4/3 ) | fair |
| Worst time | O( n2 ) | poor |
| Worst space | O( 1 ) | good |
Big O notation gives the lower, average and upper bounds of an algorithm. Time complexity bounds the number of operations; space complexity bounds the extra memory it uses.