A Sort Optimization Technique: decorate-sort-dedecorate

[xhoster at gmail.com]

Joachim Durchholz <jo at durchholz.org> wrote:
> Jim Gibson schrieb:
> >
> > The problem addressed by what is know in Perl as the 'Schwartzian
> > Transform' is that the compare operation can be an expensive one,
> > regardless of the whether the comparison uses multiple keys. Since in
> > comparison sorts, the compare operation will be executed N(logN) times,
> > it is more efficient to pre-compute a set of keys, one for each object
> > to be sorted. That need be done only N times.
>
> Wikipedia says it's going from 2NlogN to N. If a sort is massively
> dominated by the comparison, that could give a speedup of up to 100%
> (approximately - dropping the logN factor is almost irrelevant, what
> counts is losing that factor of 2).

It seems to me that ln 1,000,000 is 13.8, and that 13.8 is quite a bit
greater than 2.

Cheers,

Xho

-- 
-------------------- http://NewsReader.Com/ --------------------
Usenet Newsgroup Service                        $9.95/Month 30GB