Multiway in-place merging

We present an algorithm for asymptotically efficient k-way merging. Given an array A containing k sorted subsequences A1,…,Ak of respective lengths n1,…,nk, where , our algorithm merges A1,…,Ak into a single sorted sequence in-place and in linear time, performing ck⋅n+o(n) element comparisons and 3⋅n+o(n) element moves, where ck=⌊lgk⌋+2⋅(1−2⌊lgk⌋/k), which is a constant satisfying lgk≤ck≤⌈lgk⌉ and, moreover, bounded by ck≤lgk+0.0861. The algorithm does not merge stably, however, it does not require that the elements in A are all distinct.