K-way merge algorithm: Difference between revisions

Revision as of 14:21, 30 April 2023

Revision as of 15:02, 8 March 2024

Line 163:

=== Lower bound on running time ===

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, and n being the total number of elements. (Excluding data with desirable distributions such as disjoint ranges.) The proof is a 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. 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'')). This is a contradiction to the well-known result that no comparison-based sorting algorithm with a worst case running time below ''O''(''n'' log ''n'') exists.

(Excluding data with desirable distributions such as disjoint ranges.)

The proof is a 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.

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)).

This is a contradiction to the well-known result that no comparison-based sorting algorithm with a worst case running time below O(n log n) exists.

== External sorting ==