9.4 Shellsort

• Invented by David Shell. Also called as Diminishing Increments sort.

  REF.

  Shell. A High-speed Sorting Procedure.
  Communications of the ACM, Volume 2, Number 7, pp. 30-32,1959.

• The algorithm works by comparing elements that are distant; the distance between comparisons decreases as the algorithm runs until the last phase, in which adjacent elements are compared.

• Uses an increment sequence, h₁, h₂,..., h_t. Any increment sequence will do as long as h₁ = 1, however some choices are better than others.

• After a phase, using some increment h_k, for every i, we have
  a[i] $$\leq$$ a[i + h_k]   whenever   i + h_k $$\leq$$ n
  That is, all elements spaced h apart are sorted and the sequence is said to be
  h_k - sorted

• The following shows an array after some phases in shellsort.

  OriginalArray	81	94	11	96	12	35	17	95	28	58	41	75	15
  After5-Sort	35	17	11	28	12	41	75	15	96	58	81	94	95
  After3-Sort	28	12	11	35	15	41	58	17	94	75	81	96	95
  After1-Sort	11	12	15	17	28	35	41	58	75	81	94	95	96

• An important property of Shellsort:
  • A sequence which is h_k - sorted that is then h_{k - 1} - sorted will remain h_k - sorted.
  This means that work done by early phases is not undone by later phases.

• The action of an h_k - sorted is to perform an insertion sort on h_k independent subarrays.

• Shell suggested the increment sequence
  h_t = $$\lfloor$$$${\frac{n}{2}}$$$$\rfloor$$;h_k = $$\lfloor$$$${\frac{h_{k=1}}{2}}$$$$\rfloor$$
  For various reasons, this turns out to be a poor choice of increments. Hibbard suggested a better sequence; 1, 3, 7,...2^k - 1.

• Worst-case running time of Shellsort, using shell's increments, has been shown to be O(n²)

• Worst-case running time of Shellsort, using Hibbard's increments, has been shown to be O(n^1.5)

• Sedgewick has proposed several increment sequences that give an O(n^{${\frac{4}{3}}$} worst-case running time.

• Showing the average -case complexity of shellsort has proved to be a formidable theoretical challenge.

• Far more details, refer [weiss94, chapter 7, 256-260] and [knuth 73].