Shellsort

Jump to navigation Jump to search
 This is a stub or unfinished. Contribute by editing me.

Shellsort is a sorting algorithm that improves upon insertion sort. Shellsort uses a number of passes of h-sorting which has the property that, for some value of h, every element on the h-interval is in sorted order, no matter where you start counting. The choice for values of h is an ongoing research problem; Knuth recommends the sequence ${\displaystyle (3^{n}-1)/2}$ (whose first few terms are 1 4 13 40...). It can be generated by ${\displaystyle a_{n+1}=3a_{n}+1}$. Donald Shell, the inventor of the algorithm, originally used the powers of two (1 2 4 8 16 32..) but this was found to be quite slow because (among other reasons) no even-indexed item will be swapped with an odd-indexed item until the final pass where h = 1.

References
1. Robert Sedgewick. Algorithms in C++, Third Edition. Addison-Wesley, 1998. ISBN 0-201-35088-2. Pages 285–293 of section 6.6: Shellsort.