# 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)$

## 2 Answers

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.

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)$

• "its number of operations is equal to the number of comparisons it does" -- I doubt that. – Raphael May 5 '16 at 19:15
• "the best case running time is close to O(n log(n))" -- that does not make any sense. Did you mean to use a $\Theta$? – Raphael May 5 '16 at 19:15
• Where is that quote from? Note how it says something about the average case, not the best case. – Raphael May 5 '16 at 19:16
• I thought that the best gapping for shell sort gives $\Theta(n\log^2(n))$. – Evil May 5 '16 at 20:23
• @EvilJS, yes, using randomized shell sort it comes out to log2n for the gapping overhead. – Johan May 5 '16 at 22:12

The best case is O(n). Here's why:

Let's start with insertion sort. An already sorted list of n entries will require n minus 1 comparisons to complete (no exchanges necessary).

Put the insertion sort in the context of a shellsort with a single increment - 1. An already sorted list of n entries will require n minus the gap (1).

Suppose you have two gaps 5 followed by 1 and n is greater than 5. An already sorted list will require n-5 comparisons to process the first gap (no exchanges necessary) plus n-1 comparisons for the second or 2n-6 (no exchanges necessary).

So the algorithm for the best case is "n*number of gaps - the sum of all gaps".

I don't see how "n*number of gaps - ..." could be anything other than O(n).

I know most discussions put it as something else and I get the impression that no one has bothered to sit down and do the math. As you can see, it's not rocket science.

• Welcome to the site. If you're going to claim that everybody else is wrong because they've not bothered to do the math, you need a pretty convincing argument. Your argument seems to hinge on "I don't see how...", which I don't find it very convincing at all. – David Richerby May 10 '17 at 21:22
• Thank you. Actually, the argument is "n*number of gaps - ..." and please, if you can explain that this is about O(n log n) and not O(n) I would be very grateful. I make mistakes, same as everyone else, and if the best case/gap reasoning I have put forward here is faulty, doesn't apply to shellsort or perhaps even non-existent tell me and I will mend my ways. – Olof Forshell May 11 '17 at 8:14
• Some people do do the math. I have seen questions from people that (to me) appear to be students and they have done the math and get O(n) but become confused when everyone replies with O(n log n). – Olof Forshell May 11 '17 at 8:18
• I'm not any kind of an expert on Shell sort but doesn't one generally use about $\log n$ different gap values for sorting a length-$n$ array? The sequences listed by Wikipedia mostly grow exponentially. – David Richerby May 11 '17 at 14:11
• I think we may be discussing different things. You mention the gap sequence which is one aspect in that given a list of n randomly ordered entries there is a specific gap sequence that orders them most efficiently (i e with a minimum average number of comparisons). What I am referring to is the exact ordering of a list of n entries that shellsort handles most efficiently, regardless of the gap sequence applied and that is a list that is already ordered in the intended direction and I make the case that the number of comparisons necessary to run through it is O(n) related. – Olof Forshell May 11 '17 at 19:26