W3C home > Mailing lists > Public > www-style@w3.org > May 2010

Re: Box Reordering

From: Boris Zbarsky <bzbarsky@MIT.EDU>
Date: Mon, 24 May 2010 23:39:38 -0400
Message-ID: <4BFB467A.2050300@mit.edu>
To: "Tab Atkins Jr." <jackalmage@gmail.com>
CC: Alex Mogilevsky <alexmog@microsoft.com>, James Robinson <jamesr@chromium.org>, www-style list <www-style@w3.org>
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
Received on Tuesday, 25 May 2010 03:40:14 GMT

This archive was generated by hypermail 2.3.1 : Tuesday, 26 March 2013 17:20:27 GMT