Merge algorithm: Difference between revisions

Revision as of 22:22, 23 July 2005

Latest revision as of 18:45, 18 June 2025

(215 intermediate revisions by more than 100 users not shown)

Line 1:

{{Short description|Algorithm that combines multiple sorted lists into one}}

__NOTOC__

'''Merge algorithms''' are a family of [[algorithm|algorithms]]s that run sequentially overtake multiple [[sortsorting algorithm|sorted]] lists, typicallyas producinginput moreand sortedproduce listsa single list as output., containing Thisall isthe well-suitedelements forof machinesthe withinputs [[tapelists drive]]s.in sorted Useorder. hasThese declinedalgorithms dueare toused largeas [[randomsubroutine]]s accessin memory|randomvarious access[[sorting memoriesalgorithm]]s, andmost many applications offamously [[merge algorithms have faster alternatives when you have a random-access memory that holds all your datasort]].

== Application ==

The general merge algorithm has a [[set]] of [[pointer]]s p_0..n that point to positions in a set of lists L_0..n. Initially they point to the first item in each list. The algorithm is as follows:

[[File:Merge sort algorithm diagram.svg|thumb|upright=1.5|A graph exemplifying merge sort. Two red arrows starting from the same node indicate a split, while two green arrows ending at the same node correspond to an execution of the merge algorithm.]]

The merge algorithm plays a critical role in the [[merge sort]] algorithm, a [[comparison sort|comparison-based sorting algorithm]]. Conceptually, the merge sort algorithm consists of two steps:

# [[Recursion (computer science)|Recursively]] divide the list into sublists of (roughly) equal length, until each sublist contains only one element, or in the case of iterative (bottom up) merge sort, consider a list of ''n'' elements as ''n'' sub-lists of size 1. A list containing a single element is, by definition, sorted.

While any of p_0..n still point to data inside of L_0..n instead of past the end:

# Repeatedly merge sublists to create a new sorted sublist until the single list contains all elements. The single list is the sorted list.

# do something with the data items p_0..n point to in their respective lists

# find out which of those pointers points to the item with the lowest key; advance one of those pointers to the next item in its list

The merge algorithm is used repeatedly in the merge sort algorithm.

==Pseudocode==

A simple non-recursive pseudocode implementation of merge with two lists might be written as follows:

An example merge sort is given in the illustration. It starts with an unsorted array of 7 integers. The array is divided into 7 partitions; each partition contains 1 element and is sorted. The sorted partitions are then merged to produce larger, sorted, partitions, until 1 partition, the sorted array, is left.

'''function''' merge(a, b)

'''var''' ''list'' result

== Merging two lists ==

'''var''' ''int'' i, j, k = 0

'''if''' length(a) = 0

Merging two sorted lists into one can be done in [[linear time]] and linear or constant space (depending on the data access model). The following [[pseudocode]] demonstrates an algorithm that merges input lists (either [[linked list]]s or [[Array data structure|arrays]]) {{mvar|A}} and {{mvar|B}} into a new list {{mvar|C}}.<ref name="skiena">{{cite book |last=Skiena |first=Steven |author-link=Steven Skiena |title=The Algorithm Design Manual |publisher=[[Springer Science+Business Media]] |edition=2nd |year=2010 |isbn=978-1-849-96720-4 |page=123}}</ref>{{r|toolbox}}{{rp|104}} The function {{mono|head}} yields the first element of a list; "dropping" an element means removing it from its list, typically by incrementing a pointer or index.

'''return''' b

'''if''' length(b) = 0

'''algorithm''' merge(A, B) '''is'''

'''return''' a

'''inputs''' A, B : list

'''while''' (i < length(a)) '''andreturns''' (j < length(b))list

'''if''' a[i] <= b[j]

C := new empty list

add a[i] to result

'''while''' A is not empty and B is not empty '''do'''

i = i + 1

'''if''' head(A) ≤ head(B) '''then'''

'''else'''

append head(A) to C

add b[j] to result

drop the head of A

j = j + 1

'''else'''

append head(B) to C

drop the head of B

''// By now, either A or B is empty. It remains to empty the other input list.''

'''while''' A is not empty '''do'''

append head(A) to C

drop the head of A

'''while''' B is not empty '''do'''

append head(B) to C

drop the head of B

'''whilereturn''' i < length(a)C

add a[i] to result

'''while''' j < length(b)

add b[j] to result

'''return''' result

When the inputs are linked lists, this algorithm can be implemented to use only a constant amount of working space; the pointers in the lists' nodes can be reused for bookkeeping and for constructing the final merged list.

==Analysis==

Merge algorithms generally run in time proportional to the sum of the lengths of the lists; merge algorithms that operate on large numbers of lists at once will multiply the sum of the lengths of the lists by the time to figure out which of the pointers points to the lowest item, which can be accomplished with a [[heap]]-based [[priority queue]] in [[Big O notation|O]](lg&nbsp;''n'') time, for O(''m''&nbsp;lg&nbsp;''n'') time (where ''m'' is the sum of the lengths of the lists, and ''lg'' is ''log'' base&nbsp;2).

In the merge sort algorithm, this [[subroutine]] is typically used to merge two sub-arrays {{mono|A[lo..mid]}}, {{mono|A[mid+1..hi]}} of a single array {{mono|A}}. This can be done by copying the sub-arrays into a temporary array, then applying the merge algorithm above.{{r|skiena}} The allocation of a temporary array can be avoided, but at the expense of speed and programming ease. Various in-place merge algorithms have been devised,<ref>{{cite journal |last1=Katajainen |first1=Jyrki |first2=Tomi |last2=Pasanen |first3=Jukka |last3=Teuhola |title=Practical in-place mergesort |journal=Nordic J. Computing |volume=3 |issue=1 |year=1996 |pages=27–40 |citeseerx=10.1.1.22.8523}}</ref> sometimes sacrificing the linear-time bound to produce an {{math|''O''(''n'' log ''n'')}} algorithm;<ref>{{Cite conference| doi = 10.1007/978-3-540-30140-0_63| title = Stable Minimum Storage Merging by Symmetric Comparisons| conference = European Symp. Algorithms| volume = 3221| pages = 714–723| series = Lecture Notes in Computer Science| year = 2004| last1 = Kim | first1 = Pok-Son| last2 = Kutzner | first2 = Arne| isbn = 978-3-540-23025-0| citeseerx=10.1.1.102.4612}}</ref> see {{slink|Merge sort|Variants}} for discussion.

The classic merge (the one used in [[merge sort]]) outputs the data item with the lowest key at each step; given some sorted lists, it produces a sorted list containing all the elements in any of the input lists, and it does so in time proportional to the sum of the lengths of the input lists.

==UsesK-way merging==

{{Main|K-way merge algorithm}}

Merge can also be used for a variety of other things:

{{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}}

* given a set of current account balances and a set of transactions, both sorted by account number, produce the set of new account balances after the transactions are applied; this requires always advancing the "new transactions" pointer in preference to the "account number" pointer when the two have equal keys, and adding all the numbers on either tape with the same account number to produce the new balance.

* produce a sorted list of [[record (computer science)|record]]s with keys present in all the lists (equijoin); this requires outputting a record whenever the keys of all the p_0..n are equal.

* similarly for finding the largest number on one tape smaller than each number on another tape (e.g. to figure out what tax bracket each person is in).

* similarly for computing set differences: all the records in one list with no corresponding records in another.

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>

==Sample implementations==

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:

===[[Haskell (programming language)|Haskell ]]===

<div style="margin-left: 35px; width: 600px">

<pre>

{{framebox|blue}}

merge :: Ord a => [a]->[a]->[a]

* If {{math|''k'' {{=}} 1}}, output the single input list.

merge a [] = a

* If {{math|''k'' {{=}} 2}}, perform a binary merge.

merge [] b = b

* Else, recursively merge the first {{math|⌊''k''/2⌋}} lists and the final {{math|⌈''k''/2⌉}} lists, then binary merge these.

merge (a:as) (b:bs)

{{frame-footer}}

| a <= b = a : merge as (b:bs)

</div>

| otherwise = b : merge (a:as) bs

</pre>

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}}

== Parallel merge ==

A [[task parallelism|parallel]] version of the binary merge algorithm can serve as a building block of a [[Merge sort#Parallel merge sort|parallel merge sort]]. The following pseudocode demonstrates this algorithm in a [[fork–join model|parallel divide-and-conquer]] style (adapted from Cormen ''et al.''<ref name="clrs">{{Introduction to Algorithms|3}}</ref>{{rp|800}}). It operates on two sorted arrays {{mvar|A}} and {{mvar|B}} and writes the sorted output to array {{mvar|C}}. The notation {{mono|A[i...j]}} denotes the part of {{mvar|A}} from index {{mvar|i}} through {{mvar|j}}, exclusive.

'''algorithm''' merge(A[i...j], B[k...ℓ], C[p...q]) '''is'''

'''inputs''' A, B, C : array

i, j, k, ℓ, p, q : indices

'''let''' m = j - i,

n = ℓ - k

'''if''' m < n '''then'''

swap A and B ''// ensure that A is the larger array: i, j still belong to A; k, ℓ to B''

swap m and n

'''if''' m ≤ 0 '''then'''

'''return''' ''// base case, nothing to merge''

'''let''' r = ⌊(i + j)/2⌋

'''let''' s = binary-search(A[r], B[k...ℓ])

'''let''' t = p + (r - i) + (s - k)

C[t] = A[r]

'''in parallel do'''

merge(A[i...r], B[k...s], C[p...t])

merge(A[r+1...j], B[s...ℓ], C[t+1...q])

The algorithm operates by splitting either {{mvar|A}} or {{mvar|B}}, whichever is larger, into (nearly) equal halves. It then splits the other array into a part with values smaller than the midpoint of the first, and a part with larger or equal values. (The [[binary search]] subroutine returns the index in {{mvar|B}} where {{math|''A''[''r'']}} would be, if it were in {{mvar|B}}; that this always a number between {{mvar|k}} and {{mvar|ℓ}}.) Finally, each pair of halves is merged [[Divide and conquer algorithm|recursively]], and since the recursive calls are independent of each other, they can be done in parallel. Hybrid approach, where serial algorithm is used for recursion base case has been shown to perform well in practice <ref name="vjd">{{citation| author=Victor J. Duvanenko| title=Parallel Merge| journal=Dr. Dobb's Journal| date=2011| url=http://www.drdobbs.com/parallel/parallel-merge/229204454}}</ref>

===[[SML_programming_language|Standard ML]]===

The [[Analysis of parallel algorithms#Overview|work]] performed by the algorithm for two arrays holding a total of {{mvar|n}} elements, i.e., the running time of a serial version of it, is {{math|''O''(''n'')}}. This is optimal since {{mvar|n}} elements need to be copied into {{mvar|C}}. To calculate the [[Analysis of parallel algorithms#Overview|span]] of the algorithm, it is necessary to derive a [[Recurrence relation]]. Since the two recursive calls of ''merge'' are in parallel, only the costlier of the two calls needs to be considered. In the worst case, the maximum number of elements in one of the recursive calls is at most <math display="inline">\frac 3 4 n</math> since the array with more elements is perfectly split in half. Adding the <math>\Theta\left( \log(n)\right)</math> cost of the Binary Search, we obtain this recurrence as an upper bound:

<pre>

fun merge a [] = a

| merge [] b = b

| merge (a as x::xs) (b as y::ys) = if x <= y then

x :: merge xs b

else

y :: merge a ys;

</pre>

<math>T_{\infty}^\text{merge}(n) = T_{\infty}^\text{merge}\left(\frac {3} {4} n\right) + \Theta\left( \log(n)\right)</math>

===[[Python (programming language)|Python]]===

The solution is <math>T_{\infty}^\text{merge}(n) = \Theta\left(\log(n)^2\right)</math>, meaning that it takes that much time on an ideal machine with an unbounded number of processors.{{r|clrs}}{{rp|801–802}}

<pre>

def merge(a, b):

if len(a) == 0: return b

if len(b) == 0: return a

if a[0] <= b[0]: return a[0:1] + merge(a[1:], b)

else: return b[0:1] + merge(a, b[1:])

</pre>

'''Note:''' The routine is not [[Sorting algorithm#Stability|stable]]: if equal items are separated by splitting {{mvar|A}} and {{mvar|B}}, they will become interleaved in {{mvar|C}}; also swapping {{mvar|A}} and {{mvar|B}} will destroy the order, if equal items are spread among both input arrays. As a result, when used for sorting, this algorithm produces a sort that is not stable.

===[[Ruby (programming language)|Ruby]]===

== defParallel merge(a, b)of two lists ==

c = []

c.push(a[0] <= b[0] ? a.shift : b.shift) until a.empty? or b.empty?

c + a + b

end

There are also algorithms that introduce parallelism within a single instance of merging of two sorted lists. These can be used in field-programmable gate arrays ([[FPGA]]s), specialized sorting circuits, as well as in modern processors with single-instruction multiple-data ([[SIMD]]) instructions.

===[[Common_Lisp|Common Lisp]]===

Existing parallel algorithms are based on modifications of the merge part of either the [[bitonic sorter]] or [[odd-even mergesort]].<ref name="flimsj">{{cite journal |last1=Papaphilippou |first1=Philippos |last2=Luk |first2=Wayne |last3=Brooks |first3=Chris |title=FLiMS: a Fast Lightweight 2-way Merger for Sorting |journal=IEEE Transactions on Computers |date=2022 |pages=1–12 |doi=10.1109/TC.2022.3146509|hdl=10044/1/95271 |s2cid=245669103 |hdl-access=free |arxiv=2112.05607 }}</ref> In 2018, Saitoh M. et al. introduced MMS <ref>{{cite book |last1=Saitoh |first1=Makoto |last2=Elsayed |first2=Elsayed A. |last3=Chu |first3=Thiem Van |last4=Mashimo |first4=Susumu |last5=Kise |first5=Kenji |title=2018 IEEE 26th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM) |chapter=A High-Performance and Cost-Effective Hardware Merge Sorter without Feedback Datapath |date=April 2018 |pages=197–204 |doi=10.1109/FCCM.2018.00038|isbn=978-1-5386-5522-1 |s2cid=52195866 }}</ref> for FPGAs, which focused on removing a multi-cycle feedback datapath that prevented efficient pipelining in hardware. Also in 2018, Papaphilippou P. et al. introduced FLiMS <ref name="flimsj" /> that improved the hardware utilization and performance by only requiring <math>\log_2(P)+1</math> pipeline stages of {{math|''P/2''}} compare-and-swap units to merge with a parallelism of {{math|''P''}} elements per FPGA cycle.

<pre>

(defun mergelists (l1 l2)

(cond ((null l1) l2)

((null l2) l1)

((< (car l1) (car l2)) (cons (car l1) (mergelists (cdr l1) l2)))

(t (cons (car l2) (mergelists l1 (cdr l2))))))

</pre>

== Language support ==

'''N.B.:''' The built-in function <tt>merge</tt> allows for more types and a different comparison operator.

Some [[computer language]]s provide built-in or library support for merging sorted [[Collection (abstract data type)|collections]].

===[[C (programming language)|C]]===

=== C++ ===

<pre>

The [[C++]]'s [[Standard Template Library]] has the function {{mono|std::merge}}, which merges two sorted ranges of [[iterator]]s, and {{mono|std::inplace_merge}}, which merges two consecutive sorted ranges ''in-place''. In addition, the {{mono|std::list}} (linked list) class has its own {{mono|merge}} method which merges another list into itself. The type of the elements merged must support the less-than ({{mono|<}}) operator, or it must be provided with a custom comparator.

void Merge(float v[], int start, int mid, int end)

{

int i, j, k;

float* tmp = malloc(sizeof(float) * (end - start));

i = start;

j = mid;

k = 0;

while ((i < mid) && (j < end))

{

if (v[i] <= v[j])

tmp[k++] = v[i++];

else

tmp[k++] = v[j++];

}

while (i < mid)

tmp[k++] = v[i++];

while (j < end)

tmp[k++] = v[j++];

for (i = 0; i < (end-start); i++)

v[start+i] = tmp[i];

free(tmp);

}

</pre>

C++17 allows for differing execution policies, namely sequential, parallel, and parallel-unsequenced.<ref>{{cite web| url=http://en.cppreference.com/w/cpp/algorithm/merge| title=std:merge| publisher=cppreference.com| date=2018-01-08| access-date=2018-04-28}}</ref>

===[[C_Plus_Plus|C++]]===

=== Python ===

The below code is a straight rewrite of the above C implementation (previously billed as C/C++) into a more idiomatic C++ form.

[[Python (programming language)|Python]]'s standard library (since 2.6) also has a {{mono|merge}} function in the {{mono|heapq}} module, that takes multiple sorted iterables, and merges them into a single iterator.<ref>{{cite web| url = https://docs.python.org/library/heapq.html#heapq.merge| title = heapq — Heap queue algorithm — Python 3.10.1 documentation}}</ref>

== See also ==

<pre>

* [[Merge (revision control)]]

void Merge(float v[], int start, int mid, int end)

* [[Join (relational algebra)]]

{

* [[Join (SQL)]]

int i(start),

* [[Join (Unix)]]

j(mid),

k(0);

float * tmp(new float[end - start]);

== References ==

while(i < mid && j < end)

{{Reflist}}

{

if(v[i] <= v[j])

tmp[k++] = v[i++];

else

tmp[k++] = v[j++];

}

while(i < mid)

tmp[k++] = v[i++];

while(j < end)

tmp[k++] = v[j++];

for(i = 0; i < (end - start); ++i)

v[start + i] = tmp[i];

== Further reading ==

delete[] tmp;

* [[Donald Knuth]]. ''[[The Art of Computer Programming]]'', Volume 3: ''Sorting and Searching'', Third Edition. Addison-Wesley, 1997. {{ISBN|0-201-89685-0}}. Pages 158–160 of section 5.2.4: Sorting by Merging. Section 5.3.2: Minimum-Comparison Merging, pp.&nbsp;197–207.

}

</pre>

==External links==

Please note that the C++ [[Standard Template Library]] provides <code>std::merge</code> to accomplish this task. The library implementation is more efficient and generalized. You should never reinvent the wheel unless you absolutely must.

*[https://duvanenko.tech.blog/2018/05/23/faster-sorting-in-c/ High Performance Implementation] of Parallel and Serial Merge in [[C Sharp (programming language)|C#]] with source in [https://github.com/DragonSpit/HPCsharp/ GitHub] and in [[C++]] [https://github.com/DragonSpit/ParallelAlgorithms GitHub]

{{sorting}}

===[[Java_programming_language|Java]]===

{{DEFAULTSORT:Merge Algorithm}}

<pre>

[[Category:Articles with example pseudocode]]

void Merge(float[] array, int start, int mid, int end)

[[Category:Sorting algorithms]]

{

int i = start;

int j = mid;

int k = 0;

float[] temp = new float[end - start];

while ((i < mid) && (j < end))

if (array[i] <= array[j])

temp[k++] = array[i++];

else

temp[k++] = array[j++];

while (i < mid)

temp[k++] = array[i++];

while (j < end)

temp[k++] = array[j++];

for (i = start; i < end; i++)

array[i] = temp[i - start];

}

</pre>