Improved upper bounds on shellsort

Janet Incerpi, Robert Sedgewick

Research output: Contribution to journalArticlepeer-review

27 Scopus citations


The running time of Shellsort, with the number of passes restricted to O(log N), was thought for some time to be Θ(N 3 2), due to general results of Pratt. Sedgewick recently gave an O(N 4 3) bound, but extensions of his method to provide better bounds seem to require new results on a classical problem in number theory. In this paper, we use a different approach to achieve O(N1 + ε √1g N) for any ε0.

Original languageEnglish (US)
Pages (from-to)210-224
Number of pages15
JournalJournal of Computer and System Sciences
Issue number2
StatePublished - Oct 1985

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science
  • Applied Mathematics
  • Computer Networks and Communications
  • Computational Theory and Mathematics


Dive into the research topics of 'Improved upper bounds on shellsort'. Together they form a unique fingerprint.

Cite this