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 2 Time Complexity
Time Complexity (category)Polynomial Time -- O(n^k) 1 Connections
Credited To
Source Wikipedia: Shellsort
In Field
Invented By
Source Wikipedia: Shellsort
Sources
1. Shell Sort (Wikipedia)
Wikipedia infobox: time complexity polynomialQuote, Wikipedia infobox: time complexity polynomial
polynomial
2. Wikipedia: Shellsort
Infobox: average-time
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 SourceWikidata: Shell Sort
Wikidata Q848955, class allow-list match (w-wdresolver-0926)View the Source Reader 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.