An Analysis of $(h, k, 1)$-Shellsort
Journal of Algorithms, 1 (1):
14--50 (1980)DOI: 10.1016/0196-6774(80)90003-6
Abstract
One classical sorting algorithm, whose performance in many cases remains unanalyzed, is Shellsort. Let h be a t-component vector of positive integers. An h-Shellsort will sort any given n elements in t passes, by means of comparisons and exchanges of elements. Let S>j(h; n) denote the average number of element exchanges in the jth pass, assuming that all the n! initial orderings are equally likely. In this paper we derive asymptotic formulas of Sj(h; n) for any fixed h = (h, k, l), making use of a new combinatorial interpretation of S3. For the special case h = (3, 2, 1), the analysis is further sharpened to yield exact expressions.
