NIST

two-way merge sort

(algorithm)

Definition: A k-way merge sort that sorts a data stream using repeated merges. It distributes the input into two streams by repeatedly reading a block of input that fits in memory, a run, sorting it, then writing it to the next stream. It merges runs from the two streams into an output stream. It then repeatedly distributes the runs in the output stream to the two streams and merges them until there is a single sorted output.

See also balanced two-way merge sort, merge sort, simple merge, balanced merge sort, nonbalanced merge sort.

Note: This is an external 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 16 May 2005.
HTML page formatted Tue May 6 13:48:56 2014.

Cite this as:
Art S. Kagel, "two-way merge sort", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 16 May 2005. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/twowaymrgsrt.html