Re: Smart sorting algorithm ?

[dewar@gnat.com (Robert Dewar)]

"Tarjei T. Jensen" <tarjei.jensen@kvaerner.com> wrote in message news:<aft22d$bcm2@news.kvaerner.com>...
> Wes Groleau wrote:
> > > have a look into D.E.Knuth: The Art of Computer Programming, Vol
> > > 3: Sorting and Searching. Subsection 5.3.1: Minimum Comparison
> > > Sorting.
> >
> > Thanks, I will do that if I can find it.
> > (I got volume one at a garage sale, and
> > I've never seen any of the others anywhere.)
> 
> Knuth is an excellent example of a bit twiddler in action. As far as I'm
> concerned the point gets lost in a sea of details written in mix.

Not at all. I suspect you have not really made an effort to read these
books carefully. The point of the MIX sections (which are a very small
fraction of the material) is to try to analyze *actual* performance of
algorithms as opposed to theoretical O(f(n)) behavior. It's an interesting
attempt, not made by any other algorithm book author, and indeed not always
successful since it involves going to a very low level, but it is not clear
that there is any way of doing this that would be more successful.

In fact all algorithms in Knuth are stated in a very readable pseudo-language
and if you do not care for the detailed performance analysis in the MIX
code sections, just skip them, but don't throw out the baby with the bath
water, and don't use the MIX sections as an excuse not to thoroughly read
the material in the first three Knuth volumes (and if you have the math,
follow through the mathematical reasoning carefully).