4 ms·

It is impossible to get anything better than a constant improvement, if you divide you work by a constant factor.

• brudgers 12y ago
  Not discussing that is a weakness of the article. The algorithm addresses performance issues caused by the IO bottleneck, not an algorithmic deficiency with common merge-sort implementations. The merits and deficits of trading-off O(n)[Memory] growth for 0(log n)^2[Time] growth are worthy of discussion if it is anticipated that people will implement the algorithm in production code. There's a case for looking at it, certainly, on constrained systems, but such systems may not have processors with the execution pipeline sophistication of an Intel i7 quad-core. Which of course is just a round about way of saying, the article doesn't indicate domains in which the algorithm may be relevant and not relevant.
• sp332 12y ago
  That's just what brudgers said. But don't worry, CPU and GPU manufacturers are increasing the number of cores exponentially :p