K-way merge algorithm: Difference between revisions

Revision as of 15:41, 15 December 2016

Revision as of 15:42, 15 December 2016

Line 36:

# This repeats until all lists are empty

The head elements are generally stored in a priority queue. Depending on how the priority queue is implemented, the running time can vary. If ideal merge keeps its information in a sorted list, then inserting a new head element to the list would be done through a [[Linear search]] and the running time will be Θ(Mk • Nn) where Nn is the total number of elements in the sorted lists, and Mk is the total number of sorted lists.

On the other hand, if the sorted items in a [[Heap (data structure)|heap]], then the running time becomes Θ(Nn log Mk).

=== Binary Tree Implementation ===