A Sort Optimization Technique: decorate-sort-dedecorate

[Joachim Durchholz]

Gabriel Genellina schrieb:
> At Tuesday 29/8/2006 07:50, Joachim Durchholz wrote:
> 
>> 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).
> 
> In fact it's the other way - losing a factor of 2 is irrelevant, 
> O(2N)=O(N). The logN factor is crucial here.

That's just a question of what you're interested in.

If it's asymptotic behavior, then the O(logN) factor is a difference.

If it's practical speed, a constant factor of 2 is far more relevant 
than any O(logN) factor.

(I'm not on the list, so I won't see responses unless specifically CC'd.)

Regards,
Jo