Conference rusure::math

The question is hardly answerable as stated. By worst case I assume he means
"initial ordering of the data which requires the max. number of exchanges",
but that can only be discussed AFTER a choice of increments is made. Shell
sort can be made to be arbitrarily bad by a stupid choice of increments,
for example if many increments have the same value.

-LDY-

What is meant is this: pick some increments.  Then find the
worst case permutation.  Since Knuth says this is a hard problem,
you might simplify things by analyzing just certain types of
increments; or say the case of 2  (or 3) increments.

Finding a worst case is hard, but for "reasonable" choices of increments shell
sort is always n log n, I believe.

Here is a funny way to look at shell sort, which was what finally convinced me
(at the gut level) that shell sort works:  Shell sort is really just merge sort
done in a funny way!  Rather than taking the first half and the second half,
sorting them, and merging, you take, say, every 5th element to make 5 subfiles,
sort them, and do a 5-way merge.  This isn't QUITE what is going on, but you
can make it go through (it's years since I did this).  The number of passes
over the data is fixed by the number of increments you use, and you need log n
of them.  At each increment, you only need one pass over the data...

							-- Jerry

The best worst-case data we have is in Knuth Vol 3, p.91-92, Theorem P:
The running time for Shellsort is O(N^(3/2)) under certain conditions.
That's NOT N*log(N). - Lynn Yarbrough

Reading on, ...

"If the increments are chosen to be the set of all numbers of the form 2^p 3^q
which are less than N, the running time ... is of order N(logN)^2."

Knuth mentions that Pratt has analyzed several similar sequences; presumably,
the above gives the lowest known worst-case analysis for a choice of increments
at the time of publication.

					- Gilbert