Institution: Stanford University, Department of Computer Science

Title: An analysis of (h,k,l)-shellsort

Author: Yao, Andrew Chi-Chih

Date: March 1979

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.

http://i.stanford.edu/pub/cstr/reports/cs/tr/79/726/CS-TR-79-726.pdf