A Sort Optimization Technique: decorate-sort-dedecorate

[Joachim Durchholz]

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).

Regards,
Jo