A new upper bound for Shellsort

Robert Sedgewick

Research output: Contribution to journalArticlepeer-review

24 Scopus citations

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(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.

Original languageEnglish (US)
Pages (from-to)159-173
Number of pages15
JournalJournal of Algorithms
Volume7
Issue number2
DOIs
StatePublished - Jun 1986

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'A new upper bound for Shellsort'. Together they form a unique fingerprint.

Cite this