# 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={a1, ..., an} and B={b1, ..., bm}, each sorted according to some total order, ≤. The output is a single sequence, merge(A,B), which is a sorted permutation of {a1, ..., an, b1, ..., bm}.

merge(A, B) is

1. A, if B is empty,
2. B, if A is empty,
3. {a1}.merge({a2, ..., an}, B) if a1 <= b1, and
4. {b1}.merge(A, {b2, ..., bm}) otherwise.
The symbol "." stands for concatenation, for example, {a1, ..., an}.{b1, ..., bm} = {a1, ..., an, b1, ..., bm}.

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.

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