Re: Smart sorting algorithm ?

[Wes Groleau <wesgroleau@despammed.com>]

> > The reason I'm asking is that I have a situation
> > where deciding the order of two items is very slow.
> >
> > If the program determines that A < B  and later
> > determines that B < C and stores this information,
> > then if and when A ? C comes up, it can determine
> > the answer from the stored information.
> 
> Using, e.g., qsort, isn't it true that this should not happen?  If
> you've compared A vs B and B vs C, then B is the pivot, and A and C
> are on opposite sides of the pivot and won't get compared.

Interesting point.  On a test of 18 items,
one sort took 42 compares.  Another test
of 18 items took 76 compares.  And a test
of 36 items to 172 compares.  I've discarded
detailed logs, but it seems to me I saw several
times the same two items being compared.

This is a variation of quicksort where only one
of the two slices is recursive.  Author claims
it saves a heck of a lot of memory.  I don't really
care about memory, but it was the first open
source Ada sort in my search results.

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