Re: Smart sorting algorithm ?

[Wes Groleau <wesgroleau@despammed.com>]

> I think that's an optimization of the tight inner loop that is based on
> the assumption that one extra item compare is less expensive than
> comparing indexes on every iteration of the loop plus keeping track of
> where your pivot element is.  That comparison of an element with itself
> will end the inner loop.  In your case, the assumption is maybe not
> true, but you get at most one extra compare on the last time through the
> loop.  I think you can change the loop to save the comparison, but it
> makes the algorithm more complicated and it's easy to get it wrong.  I
> believe I've done that.

Actually, once someone gave me the clue-by-four
of "insertion with binary search" I re-wrote it
that way in less than two hours, under 50 SLOC
(including assertions).  Far simpler than the
quicksort I borrowed, and no compare (X,X).

-- 
Wes Groleau
http://freepages.rootsweb.com/~wgroleau