Shellsort

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

A.1<=A.2<=...<=A.N

ALGORITHM
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

H=...,1093,364,121,40,13,4,1

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).

PRACTICE
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

IMPLEMENTATION
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

A.1<=A.2<=...<=A.N

 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     end     A.J = V   end end return

CONNECTIONS
Sorting Problem
Counting sort
Heapsort
Quicksort
Merging

Literatura
Rich R. P. Internal Sorting Methods Illustrated with PL/1 Programs
Prentice Hall, Inc., Engelwood Cliffs, 1972
Sedgewick R. Algorithms