presented at Fourth Annual European Symposium on Algorithms Barcelona, September, 1996
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