Given an array A. of N elements the result of sorting the array in place is to arrange elements of A. so that


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 (H.1>H.2>...>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.


Running time in seconds for N=10000
Algorithm Max = 100 Max = 1000 Max = 40000 Max = 99999
QUICKSORT 4.66  4.53  4.89  4.59 
HEAPSORT 10.26  10.67  11.58  11.18 
SHELLSORT  7.45   8.89  10.58  10.13 
COUNTING_SORT  1.88   1.95   7.93  31.85 


Unit: nonrecursive internal subroutine
Global variables: array A. of arbitrary elements
Parameter: a positive integer N - number of elements in A.
Result: Reordering of input array such that


SHELLSORT: procedure expose A.
parse arg N
H = 1
do until H > N; H = 3 * H + 1; end
do until H = 1
  H = H % 3
  do I = H + 1 to N
    V = A.I; J = I; JmH = J - H
    do while A.JmH > V
      A.J = A.JmH; J = J - H
      if J <= H then leave
      JmH = J - H
    A.J = V


Sorting Problem
     Counting sort

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.

cover contents index main page

last modified 8th August 2001
Copyright 2000-2001 Vladimir Zabrodsky
Czech Republic.