Revision as of 13:49, 14 February 2017 edit Aepp1 (talk \| contribs) 1 edit m Typo ← Previous edit		Revision as of 17:31, 15 February 2017 edit undo Chris the speller (talk \| contribs) Autopatrolled, Extended confirmed users, Pending changes reviewers 894,124 edits m →Lower Running Time Bound: replaced: straight forward → straightforward using AWB Next edit →
Line 93: 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~~straightforward reduction from comparison-based sorting. Suppose that such an algorithm existed, then we 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.

K-way merge algorithm: Difference between revisions