Best case analysis for Shell sort The exercises in a textbook I studied asks about the best case for Shell sort. I have scribbled a derivation for the same along the margins almost two years ago. Basically I don't know if this was my own derivation or one copied from an authoritative source. 

I have elaborated upon the same below. Could you let me know if the reasoning is right here?


The least number of comparisons occur when the data is completely sorted.
For a particular value of the increment, say, $h_i$, each of the $h_i$ sub-sequences require at most one less comparison than the number of elements in the sub-sequence(as insertion sort is used) which is,${N \over h_i} - 1$ ,where N is the total number of data items.
For the given data in this situation $h_i \times \left (N \over h_i - 1 \right ) = N - h_i$ number of comparisons are needed as there are $h_i$ sub-sequences.
If the increment sequence selected is has $k$ increments(such that $h_k = 1$), the total number of comparisons required would be $C(N) \ge (N - h_i) + (N - h_2) + ... + (N - h_k) = kN - \sum h_i = O(N)$
The best case for Shell sort is when the array is already sorted.
In that case the inner loop does not need to any work and a simple comparison will be sufficient to skip the inner sort loop.  

A best case of $Θ(N)$ is reached by using a constant number of increments.
But the problem is that the best value for the gapping depends on the input. Therefore you cannot choose a single best value for the gap and must suffer a $log^2(N)$ delay due to repeated compares.    

So you are almost correct. Obviously there is no way to compare fewer than N-1 elements before we can conclude that the array is already sorted, so $Θ(N\space log^2(N) )$ it is.  

Note that this best case is for randomized Shell sort which is subtly different from the original.  

See: https://arxiv.org/pdf/0909.1037.pdf

All this means that Shell sort is not a particularly good algorithm for a (nearly) sorted array. The gapping introduces redundant compares whereas other sorting algorithms only have to go over the array once in the best case.
When the array is random, the gapping works in your favor, and these other algorithms that perform so wonderfully on a (nearly) sorted array perform at a dismal $O(N^2)$