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 then repeatedly merges the k streams and puts each merged run into one of j output streams until there is a single sorted output.
See also simple merge, balanced merge sort, nonbalanced merge sort.
Note: This is an external sort.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 16 May 2005.
HTML page formatted Fri Feb 23 10:06:07 2018.
Cite this as:
Art S. Kagel, "balanced k-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: https://www.nist.gov/dads/HTML/balanckwayms.html