Shellsort

From Algorithmist
Jump to: navigation, 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 (3^{n}-1)/2 (whose first few terms are 1 4 13 40...). It can be generated by 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[edit]
  1. Robert Sedgewick. Algorithms in C++, Third Edition. Addison-Wesley, 1998. ISBN 0-201-35088-2. Pages 285–293 of section 6.6: Shellsort.