K-way merge algorithm: Difference between revisions

Revision as of 20:32, 15 December 2016

Revision as of 22:17, 19 December 2016

Line 95:

The proof is a straight forward reduction from comparison-based sorting.

Suppose that such an algorithm existed, then we can construct a comparison-based sorting algorithm with running time O(n f(n)) as follows:

Chop the input array n into n arrays of size 1.

Merge these n arrays with the K-Way Merge algorithm.

The resulting array is sorted and the algorithm has a running time in O(n f(n)).