Shellsort will work correctly regardless of the size of the increments, *provided that the final pass has increment 1* (i.e., provided the final pass is a regular Insertion Sort). If Shellsort will always conclude with a regular Insertion Sort, then how can it be any improvement on Insertion Sort? The expectation is that each of the (relatively cheap) sublist sorts will make the list “more sorted” than it was before. It is not necessarily the case that this will be true, but it is almost always true in practice. When the final Insertion Sort is conducted, the list should be “almost sorted,” yielding a relatively cheap final Insertion Sort pass.

Thank you for answering. I was asking that all the time I was reading about `shellsort`

.

But that doesn’t necessarily mean that I am quite convinced of the usefulness of Shellsort over a regular Insertion Sort. Besides, the text continues on to state that:

The analysis of Shellsort is difficult, so we must accept without proof that the average-case performance of Shellsort (for “divisions by three” increments) is O(*n*^{1.5}). Other choices for the increment series can reduce this upper bound somewhat. Thus, Shellsort is substantially better than Insertion Sort, or any of the Θ(*n*^{2}) sorts presented [earlier].

Sure, “substantially better”. But we must accept it **without proof**.

It’s like believing in wholly in Darwin without looking at scientific evidence.

From Clifford A. Shaffer’s *A Practical Introduction to Data Structures and Algorithm Analysis Edition 3.1 (Java Version)*