Editing Merge algorithm (section)

==K-way merging==
{{Main|K-way merge algorithm}}
{{mvar|k}}-way merging generalizes binary merging to an arbitrary number {{mvar|k}} of sorted input lists. Applications of {{mvar|k}}-way merging arise in various sorting algorithms, including [[patience sorting]]<ref name="Chandramouli">{{Cite conference |last1=Chandramouli |first1=Badrish |last2=Goldstein |first2=Jonathan |title=Patience is a Virtue: Revisiting Merge and Sort on Modern Processors |conference=SIGMOD/PODS |year=2014}}</ref> and an [[external sorting]] algorithm that divides its input into {{math|''k'' {{=}} {{sfrac|1|''M''}} − 1}} blocks that fit in memory, sorts these one by one, then merges these blocks.{{r|toolbox}}{{rp|119–120}}

Several solutions to this problem exist. A naive solution is to do a loop over the {{mvar|k}} lists to pick off the minimum element each time, and repeat this loop until all lists are empty:

<div style="margin-left: 35px; width: 600px">
{{framebox|blue}}
* Input: a list of {{mvar|k}} lists.
* While any of the lists is non-empty:
** Loop over the lists to find the one with the minimum first element.
** Output the minimum element and remove it from its list.
{{frame-footer}}
</div>

[[Best, worst and average case|In the worst case]], this algorithm performs {{math|(''k''−1)(''n''−{{sfrac|''k''|2}})}} element comparisons to perform its work if there are a total of {{mvar|n}} elements in the lists.<ref name="greene">{{cite conference |last=Greene |first=William A. |year=1993 |title=k-way Merging and k-ary Sorts |conference=Proc. 31-st Annual ACM Southeast Conf |pages=127–135 |url=http://www.cs.uno.edu/people/faculty/bill/k-way-merge-n-sort-ACM-SE-Regl-1993.pdf}}</ref>
It can be improved by storing the lists in a [[priority queue]] ([[heap (data structure)|min-heap]]) keyed by their first element:

<div style="margin-left: 35px; width: 600px">
{{framebox|blue}}
* Build a min-heap {{mvar|h}} of the {{mvar|k}} lists, using the first element as the key.
* While any of the lists is non-empty:
** Let {{math|''i'' {{=}} find-min(''h'')}}.
** Output the first element of list {{mvar|i}} and remove it from its list.
** Re-heapify {{mvar|h}}.
{{frame-footer}}
</div>

Searching for the next smallest element to be output (find-min) and restoring heap order can now be done in {{math|''O''(log ''k'')}} time (more specifically, {{math|2⌊log ''k''⌋}} comparisons{{r|greene}}), and the full problem can be solved in {{math|''O''(''n'' log ''k'')}} time (approximately {{math|2''n''⌊log ''k''⌋}} comparisons).{{r|greene}}<ref name="toolbox">{{cite book|author1=Kurt Mehlhorn|author-link=Kurt Mehlhorn|author2=Peter Sanders|author2-link=Peter Sanders (computer scientist)|title=Algorithms and Data Structures: The Basic Toolbox |date=2008 |publisher=Springer |isbn=978-3-540-77978-0 |url=http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/}}</ref>{{rp|119–120}}

A third algorithm for the problem is a [[divide and conquer algorithm|divide and conquer]] solution that builds on the binary merge algorithm:

<div style="margin-left: 35px; width: 600px">
{{framebox|blue}}
* If {{math|''k'' {{=}} 1}}, output the single input list.
* If {{math|''k'' {{=}} 2}}, perform a binary merge.
* Else, recursively merge the first {{math|⌊''k''/2⌋}} lists and the final {{math|⌈''k''/2⌉}} lists, then binary merge these.
{{frame-footer}}
</div>

When the input lists to this algorithm are ordered by length, shortest first, it requires fewer than {{math|''n''⌈log ''k''⌉}} comparisons, i.e., less than half the number used by the heap-based algorithm; in practice, it may be about as fast or slow as the heap-based algorithm.{{r|greene}}