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

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 Fri Nov 30 12:16:34 2007.

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

to NIST home page