Papex

Open problem · Computer science · Open

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.

More in Computing