An analysis of (h,k, 1)-Shellsort

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 S_j(h; n) for any fixed h = (h, k, l), making use of a new combinatorial interpretation of S₃. For the special case h = (3, 2, 1), the analysis is further sharpened to yield exact expressions.