Analysis of shellsort and related algorithms

Robert Sedgewick

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

24 Scopus citations


This is an abstract of a survey talk on the theoretical and empirical studies that have been done over the past four decades on the Shellsort algorithm and its variants. The discussion includes: upper bounds, including linkages to number-theoretic properties of the algorithm; lower bounds on Shellsort and Shellsort-based networks; average-case results; proposed probabilistic sorting networks based on the algorithm; and a list of open problems.

Original languageEnglish (US)
Title of host publicationAlgorithms - ESA 1996 - 4th Annual European Symposium, Proceedings
EditorsJosep Diaz, Maria Serna
PublisherSpringer Verlag
Number of pages11
ISBN (Print)3540616802, 9783540616801
StatePublished - 1996
Event4th European Symposium on Algorithms, ESA 1996 - Barcelona, Spain
Duration: Sep 25 1996Sep 27 1996

Publication series

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


Other4th European Symposium on Algorithms, ESA 1996

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Analysis of shellsort and related algorithms'. Together they form a unique fingerprint.

Cite this