K-way merge algorithm: Difference between revisions

Revision as of 15:25, 27 March 2017

Revision as of 08:03, 7 May 2017

Line 65:

The tournament tree<ref>

{{cite book| last = Knuth| first = Donald| authorlink = Donald Knuth| series = [[The Art of Computer Programming]]| volume= 3| title= Sorting and Searching| edition = 2nd| publisher = Addison-Wesley| year= 1998| chapter = Chapter 5.4.1. Multiway Merging and Replacement Selection| pages = 158–168| isbn = 0-201-89685-0| ref = harv}}</ref> algorithmsalgorithm constructs a balanced binary tree with k leafsleaves.

Every leaf stores a pointer intoto one of the input arrays.

Further, for everyEvery node in the tree,stores a value and an index is stored.

For the k-th leaf the value is the value that its pointer points to and the index is k.

For every internal leaf the value is the minimum of the values of the node's children.

The index of an internal leaf indicates which input array the value comes from.

The root of the tournament tree contains the smallest element and the index of the corresponding input array.

The algorithm iteratively transfers this element and advances the corresponding pointer.

It then updates the values of the nodes on the path from the corresponding leaf to the root.

As the tree is balanced, this path contains only Θ(log k) elementelements.

As there n elements that need to be extracted, the resulting total running time is Θ(n log k).

the sorted items in a [[Heap (data structure)|heap]], then the running time becomes Θ(n log k).

===== Example =====