Tight lower bounds for Shellsort

Mark Allen Weiss, Robert Sedgewick

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Shellsort is a simple classic algorithm that runs competitively on both mid-sized and nearly sorted files. It uses an increment sequence, the choice of which can drastically affect the algorithm's running time. Due to the results of Pratt, the running time of Shellsort was long thought to be Θ(N3/2) for increment sequences that are “almost geometric”. However, recent results have lowered the upper bound substantially, although the new bounds were not known to be tight. In this paper, we show that an increment sequence given by Sedgewick is Θ(N4/3) by analyzing the time required to sort a particularly bad permutation. Extending this proof technique to various increment sequences seems to lead to lower bounds that in general match the known upper bounds and suggests that Shellsort runs in Ω(N1 + ∈/→log N) for increment sequences of practical interest, and that no increment sequence exists that would make Shellsort optimal.

Original languageEnglish (US)
Title of host publicationSWAT 88 - 1st Scandinavian Workshop on Algorithm Theory, Proceedings
EditorsRolf Karlsson, Andrzej Lingas
PublisherSpringer Verlag
Pages255-262
Number of pages8
ISBN (Print)9783540194873
DOIs
StatePublished - Jan 1 1988
Event1st Scandinavian Workshop on Algorithm Theory, SWAT 1988 - Halmstad, Sweden
Duration: Jul 5 1988Jul 8 1988

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume318 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other1st Scandinavian Workshop on Algorithm Theory, SWAT 1988
CountrySweden
CityHalmstad
Period7/5/887/8/88

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Tight lower bounds for Shellsort'. Together they form a unique fingerprint.

Cite this