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
