dmd 2.029 release

Andrei Alexandrescu SeeWebsiteForEmail at erdani.org
Mon Apr 20 06:52:51 PDT 2009


Andrei Alexandrescu wrote:
> Georg Wrede wrote:
>> Walter Bright wrote:
>>>
>>> This is a major revision to Phobos, including Andrei's revolutionary 
>>> new range support.
>>>
>>> http://www.digitalmars.com/d/2.0/changelog.html
>>> http://ftp.digitalmars.com/dmd.2.029.zip
>>
>> The documentation for completeSort in std.algorithm says:
>>
>>    Performs O(n * log(n)) (best case)
>>          to O(n * log(n)) (worst-case) evaluations of swap.
>>
>> I wonder what it should be.
> 
> Sorry, what was I thinking? I think (without being sure) that the
> complexity of completeSort is O(rhs.length * log(t)) in the
> best case, and O(t * log(t)) in the worst case, where t = lhs.length +
> rhs.length.

I revise that. Best case, there's temporary memory to allocate and then 
the complexity is that of sorting rhs plus merge lhs and rhs using extra 
memory. That is O(lhs.length + rhs.length * log(rhs.length)).

Worst case, there's no temporary memory available so we need to sort the 
whole thing. That means O((lhs.length + rhs.length) * log(rhs.length + 
rhs.length)).

I committed the fixed module.


Andrei


More information about the Digitalmars-d-announce mailing list