Multiway In-Place Merging

We present an algorithm for asymptotically efficient k-way merging. Given an array A containing sorted subsequences A(1), ... , A(k) Of respective lengths 711, 71k, where Ei=1 ?ti = 71., our algorithm merges A,,..., Ak in-place, into a single sorted sequence, performing [lg k] . n + o(n) element comparisons and 3 . n + 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.