(definition)

**Definition:**
Combine two or more sorted sequences of data into a single sorted sequence.

**Formal Definition:** For simplicity, let input be two sequences, A={a_{1}, ..., a_{n}} and B={b_{1}, ..., b_{m}}, each sorted according to some *total order*, ≤. The output is a single sequence, merge(A,B), which is a sorted *permutation* of {a_{1}, ..., a_{n}, b_{1}, ..., b_{m}}.

merge(A, B) is

- A, if B is empty,
- B, if A is empty,
- {a
_{1}}.merge({a_{2}, ..., a_{n}}, B) if a_{1}<= b_{1}, and - {b
_{1}}.merge(A, {b_{2}, ..., b_{m}}) otherwise.

Formalization by Mustafa Ege <ege@eti.cc.hun.edu.tr>.

**Specialization** (... is a kind of me.)

*multiway merge*, *k-way merge*, *simple merge*, *ideal merge*, *optimal merge*.

**See also**
*two-way merge sort*, *three-way merge sort*, *k-way merge sort*, *balanced merge sort*, *nonbalanced merge sort*.

Author: ASK

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 2 March 2015.

HTML page formatted Fri Feb 23 10:06:08 2018.

Cite this as:

Art S. Kagel, "merge", in
*Dictionary of Algorithms and Data Structures* [online], Vreda Pieterse and Paul E. Black, eds. 2 March 2015. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/merge.html