Re: Box Reordering

On 5/24/10 11:21 PM, Tab Atkins Jr. wrote:
>> Fwiw.... the Gecko implementation is somewhat as you described, and it's not
>> good enough for this use case if the DOM is being mutated and you have to
>> resort.  Quicksort is typically O(N log N) or worse on nearlt-sorted data,
>> so you get overall O(N^2 log N) behavior unless you add yet more complexity
>> and sort lazily, etc.
>
> Of course, there are relatively simple relatives to quicksort that
> perform well on nearly-sorted data, which is what you'll see most of
> the time here.

Unless you mean "better than O(N)" by "well", you still get quadratic 
behavior.

-Boris