A comparison sort that generalizes insertion sort by first comparing and sorting elements far apart from each other, using a shrinking gap sequence, so that later passes over closer elements have less work left to do.
Facts
Time ComplexityDepends on the gap sequence: O(n squared) worst case for the worst known sequence, O(n log^2 n) for the best known worst-case sequence 1 Connections
Sources
1. Wikipedia: Shellsort
Infobox, performance
average complexity depends on gap sequence
Lead section
The algorithm was first published by Donald Shell in 1959, and has nothing to do with shells.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.