Revision as of 22:17, 19 December 2016 edit 178.10.127.62 (talk) →Lower Running Time Bound ← Previous edit		Revision as of 22:18, 19 December 2016 edit undo 178.10.127.62 (talk) →Lower Running Time Bound Next edit →
Line 94: One can show that no comparison-based K-Way Merge algorithm exists with a running time in O(n f(k)) where f grows asymptotically slower than a logarithm. The proof is a straight forward reduction from comparison-based sorting. Suppose that such an algorithm existed, then we ~~can~~could construct a comparison-based sorting algorithm with running time O(n f(n)) as follows: Chop the input array into n arrays of size 1. Merge these n arrays with the K-Way Merge algorithm.

K-way merge algorithm: Difference between revisions