k-way merge sort


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

Also known as p-way merge sort.

Aggregate child (... is a part of or used in me.)
k-way merge.

See also balanced k-way 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 30 November 2007.
HTML page formatted Wed Mar 13 12:42:46 2019.

Cite this as:
Art S. Kagel, "k-way merge sort", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 30 November 2007. (accessed TODAY) Available from: