NIST

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.

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 Mon Mar 2 16:13:48 2015.

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: http://www.nist.gov/dads/HTML/merge.html