K-way merge algorithm: Difference between revisions

Revision as of 17:35, 19 April 2023

Latest revision as of 01:39, 8 November 2024

(5 intermediate revisions by 5 users not shown)

Line 1:

{{Short description|Sequence merge algorithm in computer science}}

{{DISPLAYTITLE:''k''-way merge algorithm}}

In [[computer science]], '''''k''-way merge algorithms''' or multiway merges are a specific type of [[Merge algorithm|sequence merge algorithms]] that specialize in taking in k sorted lists and merging them into a single sorted list. These merge algorithms generally refer to merge algorithms that take in a number of sorted lists greater than two. Two-way merges are also referred to as binary merges. The k- way merge is also an external sorting algorithm.

== Two-way merge ==

Line 40 ⟶ 41:

We can improve upon this by computing the smallest element faster.

By using either [[Heap (data structure)|heaps]], tournament trees, or [[Splay_tree|splay treestree]]s, the smallest element can be determined in O(log k) time.

The resulting running times are therefore in O(n log k).

Line 53 ⟶ 54:

|last1=Bentley

|first1=Jon Louis

|author-link=Jon_Bentley_Jon Bentley (computer_scientistcomputer scientist)

|title=Programming Pearls

|date=2000

Line 90 ⟶ 91:

When one of the leaves is updated, all games from the leaf to the root are replayed. In the following [[pseudocode]], an object oriented tree is used instead of an array because it is easier to understand. Additionally, the number of lists to merge is assumed to be a power of two.

'''function''' merge(L1, …..., Ln)

buildTree(heads of L1, …..., Ln)

'''while''' tree has elements

winner := tree.winner

Line 120 ⟶ 121:

===== Running time =====

In the beginning, the tree is first created in time Θ(k). In each step of merging, only the games on the path from the new element to the root need to be replayed. In each layer, only one comparison is needed. As the tree is balanced, the path from one of the input arrays to the root contains only Θ(log k) elements. In total, there are n elements that need to be transferred. The resulting total running time is therefore in Θ(n log k). <ref name="knuth98" />

===== Example =====

Line 163 ⟶ 164:

=== 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 ==