Re:Parallel In-Place Merge Sort
by brudgers on Wednesday October 01, 2014 @09:50AM
(#8394256)
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.
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.