In a message dated 03-18-98, Jonathan de Boyne Pollard said to David Noon
about Sort Algorithm
Hi Jonathan,
 DN> Since you now have my function template for Shell's algorithm, you
 DN> might care to give it a try. The version I posted is not O(n**2), but
 DN> O(n**1.5), so it should be significantly quicker than Combsort as the
 DN> array size increases.
JP>I find, upon re-reading the literature, that there is controversy as to 
JP>whether Shell sort is O(N**1.5) or O(N*log N).
True, but that isn't what I said.
I said that the C++ template I posted was O(n**1.5). The specific
parameterization I used has been proven to be bounded O(n**1.5).
The parameter of interest was the constant mul. In the case where it is 3,
such as in my template, Shell's algorithm is bounded O(n**1.5) for any data
stream, with improved results for more ideal data streams. For other values
of mul, Shellsort can be O(n*log n) for many data streams, but can go to
O(n**2) for some 'worst case' data streams. I simply chose a value of mul
that is known as a safe bet for all data streams.
JP>No-one has 
JP>been able to analyse the algorithm well enough to show 
JP>which -- if, indeed, either.  Since both Shell and Comb 
JP>apply the same modifications to algorithms that are 
JP>themselves O(N*N), and since this yields O(N**1.5) or 
JP>O(N*long N) in Shell's case, I suspect that, contrary to my 
JP>previous message, Comb is probably O(N**1.5) or O(N*log N) 
JP>too.
I think it will vary, just as Shell's algorithm. However, the Combsort's
underlying bubble sort takes about twice as long as insertion sort, so I
would expect Shellsort to perform slightly better the Combsort in most
cases.
JP> First, it would preclude the use of a better sort 
JP>algorithm if one were to be discovered later.
True, but the only such algorithm I know of is rather specialised (Batcher's
algorithm).
JP>Second, it 
JP>would preclude intelligent implementations from choosing 
JP>amongst multiple sort algorithms based upon array size and 
JP>VM performance constraints (The VM behaviour of an internal 
JP>sort algorithm is invariably not discussed in textbooks on 
JP>algorithmics.).
Again true.
When paging is considered, an internal sort starts to take on the
characteristics of external sorting. The optimal I/O paradigm for external
sorts uses asynchronous transfer and long read-aheads. Demand paging is
synchronous and usually just a single page frame; this makes it one of the
worst possible approaches to external sorting.
So, ideally, an internal sort should not page at all. This is, therefore,
the assumption used in books on algorithmics.
Regards
Dave

___
 * MR/2 2.25 #353 * 
PATH=C:\DOS;C:\DOS\RUN;C:\WIN\CRASH\DOS;C:\ME\DEL\WIN;C:\ME\USE\OS2 -!-
--- Maximus/2 3.01
---------------