Multiway In-Place Merging
Viliam Geffert and Jozef Gajdos
Abstract
We present an algorithm for asymptotically efficient k-way merging.
Given an array A containing sorted subsequences A_1,...,A_k of
respective lengths n_1,...,n_k, where sum_{i=1}^{k} n_i = n, our
algorithm merges A_1,...,A_k in-place, into a single sorted sequence,
performing ceil{log k} n + o(n) element comparisons and 3n + o(n)
element moves. That is, our algorithm runs in linear time, with the
number of moves independent of k, the number of input sequences.
Keywords: in-place algorithms, merging, sorting.