# merge

(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.

The symbol "." stands for concatenation, for example, {a_{1}, ..., a_{n}}.{b_{1}, ..., b_{m}} = {a_{1}, ..., a_{n}, b_{1}, ..., b_{m}}. 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

## Implementation

(Scheme)

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

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

Entry modified 30 November 2007.

HTML page formatted Tue Dec 6 16:16:32 2011.

Cite this as:

Art S. Kagel, "merge", in
*Dictionary of Algorithms and Data
Structures* [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 30 November 2007. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/merge.html