Average-case complexity of Shellsort
What is the lowest possible average running time of Shellsort with a fixed sequence of gaps?
Summary
Donald Shell published the algorithm in 1959, and its running time depends heavily on the gap sequence. For many practical gap sequences the time complexity is unknown, and none of the proven average-case results concerns a practical sequence.
Source
Open, as listed by Wikipedia · Unsolved problems in computer science. Checked 18 Nov 2026.
The status is the source’s. Papex does not decide whether a problem is solved.
Records on this problem
No public record addresses this problem yet.