TY - JOUR
T1 - A new upper bound for Shellsort
AU - Sedgewick, Robert
N1 - Funding Information:
*This research was supported in part by NSF Grant MCS-80-17579 while the author was at Brown University, and in part while the author was visiting the Institute for Defense Analyses, Princeton, NJ.
PY - 1986/6
Y1 - 1986/6
N2 - 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(N 4 3). The previous best-known upper bound for sequences of O(log N) increments was O(N 3 2), 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.
AB - 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(N 4 3). The previous best-known upper bound for sequences of O(log N) increments was O(N 3 2), 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.
UR - http://www.scopus.com/inward/record.url?scp=38249039186&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=38249039186&partnerID=8YFLogxK
U2 - 10.1016/0196-6774(86)90001-5
DO - 10.1016/0196-6774(86)90001-5
M3 - Article
AN - SCOPUS:38249039186
SN - 0196-6774
VL - 7
SP - 159
EP - 173
JO - Journal of Algorithms
JF - Journal of Algorithms
IS - 2
ER -