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