K-way merge algorithm: Difference between revisions

Revision as of 17:31, 15 February 2017

Revision as of 15:25, 27 March 2017

Line 58:

The pointers are sorted by the value that they point to.

In an O(k) preprocessing step the heap is created using the standard heapify procedure.

Afterwards, the algorithm iteratively transfers the element that the root pointer points to, increases this pointer and executes the standard increasedecrease key procedure upon the root element.

The running time of the increase key procedure is bounded by O(log k).

As there are n elements, the total running time is O(n log k).