Article,
A New Upper Bound for Shellsort
Journal of Algorithms, 7 (2): 159--173 (1986)
DOI: 10.1016/0196-6774(86)90001-5
Abstract
A direct relationship between Shellsort and the classical “problem of Frobenius” from additive number theory is used to derive a sequence of O(log N) increments for Shellsort for which the worst case running time is O(N43). The previous best-known upper bound for sequences of O(log N) increments was O(N32), which was shown by Pratt to be tight for a large family of sequences, including those commonly used in practice. The new upper bound is of theoretical interest because it suggests that increment sequences might exist which admit even better upper bounds, and of practical interest because the increment sequences which arise outperform those common used, even for random files.
