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 Wed Mar 13 12:42:46 2019.

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