BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-79-726
       ENTRY:: June 19, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: An analysis of (h,k,l)-shellsort
        TYPE:: Technical Report
      AUTHOR:: Yao, Andrew Chi-Chih
        DATE:: March 1979
       PAGES:: 58
    ABSTRACT:: One classical sorting algorithm, whose performance in many
               cases remains unanalyzed, is Shellsort. Let $\vec{h} be a
               t-component vector of positive integers. An
               $\vec{h}$-Shellsort will sort any given n elements in t
               passes, by means of comparisons and exchanges of elements.
               Let $S_j$($\vec{h}$;n) denote the average number of element
               exchanges in the j-th pass, assuming that all the n! initial
               orderings are equally likely. In this paper we derive
               asymptotic formulas of $S_j$($\vec{h}$;n) for any fixed
               $\vec{h}$ = (h,k,l), making use of a new combinatorial
               interpretation of $S_3$. For the special case $\vec{h}$ =
               (3,2,1), the analysis if further sharpened to yield exact
               expressions.
       NOTES:: [Adminitrivia V1/Prg/19950619]
         END:: STAN//CS-TR-79-726