We first sort all elements that are at distance H.1
from each other, then re-sort the array using increment H.2
, finally we do an ordinary insertion sort with increment 1
). D. L. Shell, the originator of the algorithm, took H=N%2
as the first value of H
and used the formula H=H%2
. A sequence which has been shown empirically to do well is
i.e H=(3**K-1)/2 which can be generated by the formula H=3*H+1 with the initial value H=1. The number of operations required in all is of order O(N**(3/2)) for the worst possible ordering of the original data. In average the operations count goes approximately as O(N**1.25).
The following table compares four sorting algorithms. The A. array includes integers in the range 1 to Max=10,100,1000,40000.
Rich R. P. Internal Sorting Methods Illustrated with PL/1 Programs
Prentice Hall, Inc., Engelwood Cliffs, 1972
Sedgewick R. Algorithms
Addison-Wesley, Reading, Massachusetts, 1984
I changed the test from Max=10 ... 40000 to Max=100 ... 99999. Thanks for idea go to Walter Pachl.
This test ran in the Windows 2000 Professional environment on the computer with 132MB RAM and processor x86Family 6 Mode 6 Stepping 5.