Analysis of Shellsort and Related Algorithms

Robert Sedgewick

presented at Fourth Annual European Symposium on Algorithms
Barcelona, September, 1996

Abstract

This paper surveys 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.

Comments, questions, suggestions:

   mail rs@cs.princeton.edu 

Copyright (c) 1996, Robert Sedgewick