Improved Lower Bounds for Shellsort

The authors give improved lower bounds for Shellsort based on a new and relatively simple proof idea. The lower bounds obtained are both stronger and more general than the previously known bounds. In particular, they hold for nonmonotone increment sequences and adaptive Shellsort algorithms, as well as for some recently proposed variations of Shellsort. >

Authors

• C. Greg Plaxton
• Bjorn Poonen
• Torsten Suel

Keywords

• Sorting
• Partitioning algorithms
• Mathematics
• Upper bound
• Lower Bound
• Conjecture
• Sequence Length
• Running Time
• Classification Algorithms
• Essential Step
• Less Than Or Equal
• Proof Of Theorem
• Adaptive Algorithm
• Network Size
• Block Size
• Input Files
• Constant Factor
• Formal Proof
• Number Of Definitions
• Power-of-two
• OR Operation
• Sorting Algorithm
• Arbitrary Sequence