Re: Possible F77 Code Improvement ??

On 2009-03-09 13:42:16 -0300, nmm1@xxxxxxxxx said:

In article <2009030913272716807-gsande@worldnetattnet>,
Gordon Sande <g.sande@xxxxxxxxxxxxxxxx> wrote:

Shell sort is an example of a sorting network in that the comparisons
are between fixed elements. I believe there is an analysis for these
that shows they can be n log ( n ) log log ( n ). It is the type of
thing that Don Knuth would do and I believe that one of his
students did an analysis of how to chose the step sizes in Shell sort.

Has that been proved? It has been hypothesised since Shell invented
it. It is remarkable how resilient it is to the choice of step sizes,
and the only rules seem to be to ensure that you don't choose an
exact divisor and drop by about a factor of three. I have seen at
least one student's analysis, and it was hard to write up for that
reason!

My Knuth Vol 3 (1st ed) gives n ( log n )^2 so I must be having memory problems. The student listed for sorting networks does not ring a bell. Google found Pratt for me who had done the work I was thinking of. He
gave a set of increment values for Shell sort that achieved this bound. Sedgewick's survey "Analysis of Shellsort and Related Algorithms" in 1996 seems to be a modern account.

Google gives the same facts but also has a citation of "An 0(n log n) sorting network" by M. Ajtai, J. Komlos and E. Szemeredi in 1983. A
quick scan of the first page reveals that even the authors claim that
the complexity coefficient is so large that it is not a practical method.
Google provides more literature. I thought I recalled an asymptopic
improvement (that put me to sleep when I tried reading it) on sorting
networks to n log n log log n. Clearly that has been surpassed.


Regards,
Nick Maclaren.


.

Loading