Re: Smart sorting algorithm ?

[achrist@easystreet.com]

Wes Groleau wrote:
> 
> > I guess that quicksort will repeat comparisons if there are duplicate
> > items in the set of items being sorted.  Or if the pivots are selected
> 
> As a matter of fact, this particular implementation
> _several_ times compared an item with itself!
> 

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.

Al