Re: Smart sorting algorithm ?

["Ron" <ron@no.spam>]

"Wes Groleau":
> Wrote an "<" that
> first checks a 2D lookup table.  If the
> answer is "unknown" it does the comparison,
> then updates as many cells in the table as
> possible.

Smart.  You avoid making the same comparison more than once and learn from
transitivity...  No matter what sorting algorithm you use, the table keeps
the number of comparison down to nC2=n(n-1)/2 comparisons.  The gain from
transitivity will depend upon your sorting algorithm, but some will give you
no gain at all...

> Since the actual comparison was the bottleneck,
> the choice of sorting algorithms doesn't matter
> any more.

No.  Though you never gave the range of the number of items to sort, even
for small lists the difference between the worst case (nC2 = n(n-1)/2
comparisons) and an O(nlog(n)) sorting algorithm such as heapsort
(~ceiling(ln(n!)/ln(2) for small n) is very large.  That's 86 more
comparisons for n=18 and 489 more for n=36.  You want to minimize the number
of comparisons, so you need to select a good sorting algorithm...


- Ron Zeno