Multiway in-place merging by prof. Geffert

We shall present an efficient algorithm for solving the following problem. Given an array A, containing k sorted subsequences A₁,...,A_k of respective lengths n₁,...,n_k, where n₁ +...+ n_k = n, we need to rearrange the array A into a single sorted sequence.

As a typical example, the array A may contain sorted telephone directories of Berlin, Bratislava, Bucharest, Budapest, Košice, Prague, Sofia, Štrbské Pleso, Warsaw, Zagreb, and Zurich, which should be unified into a single sorted directory. Clearly, any sorting algorithm could solve this task. However, such algorithm does not utilize the fact that our array is composed of very few subsequences that are quite long, but all sorted. Thus, a general sorting algorithm would use an unnecessarily large number of comparisons. Moreover, we require the algorithm perform the task in-place, i.e., besides the space occupied by the array A, we have a very limited additional memory available, namely, only a constant number of variables for sorted elements or indexes, no recursion.

We shall present an algorithm solving this task in-place and in linear time, performing n * lg k + o(n) element comparisons and 3 * n + o(n) element moves. Note that the number of moves is independent of k, the number of input sequences. (Here "o(n)" represents some small value, satisfying lim_n→∞ o(n)/n = 0.) It has also been shown that the above algorithm is almost optimal; no algorithm can solve this task using fewer than n*(log k) comparisons.

[V.Geffert, J.Gajdoš: Multiway in-place merging, Proc.of FCT 2009 (Fundametals of Computation Theory), Lecture Notes in Computer Science 5699, Springer-Verlag, 2009, pp.133-144]

Prof. Viliam Geffert is one of the world-known scientist in the area of computational complexity and formal languages. His main areas of interest are: grammars and descriptional complexity of automata, sorting algorithms and sublogarithmic space