A Sort Optimization Technique: decorate-sort-dedecorate

Tue Aug 29 12:24:43 EDT 2006

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.

Gabriel Genellina
Softlab SRL 

__________________________________________________
Preguntá. Respondé. Descubrí.
Todo lo que querías saber, y lo que ni imaginabas,
está en Yahoo! Respuestas (Beta).
¡Probalo ya! 
http://www.yahoo.com.ar/respuestas