Content deleted Content added
Line 35:
# After the head element of the first list is removed, it is resorted according to the value of its new head element
# This repeats until all lists are empty
Depending on how ideal merge 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 Θ(M•N) where M is the total number of elements in the sorted lists, and N 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 Θ(M log N).
== In-Place Multiway Merging ==
| |||