Merge $k$-sorted arrays - without heaps/AVL tree in $O(n\log(k))$?

Question

Given $k$-sorted arrays in ascending order, is it possible to merge all $k$ arrays to a single sorted array in $O(n\log(k))$ time where $n$ denotes all the elements combined.

The question is definitely aiming towards a Min-heap/AVL tree solution, which can in fact achieve $O(n\log(k))$ time complexity.

However i'm wondering if there exists a different approach, like a merge variant which can achieve the same result.

The closest I've seen is to merge all the arrays into one array which disregards their given ascending order, than doing comparison-based sort which takes $O(n\log(n))$ but not quite $O(n\log(k))$.

Is there an algorithm variant which can achieve this result? Or a different data-structure?

Answer 1

For the sake of avoiding dealing with rounding in the analysis, assume for simplicity that $k$ is a power of $2$ (if it is not, you can add $d \le k-1$ dummy arrays with one $+\infty$ element each, and ignore the last $d$ elements in the final sorted vector).

You can merge your arrays two by two in a binary-tree fashion: the algorithm works in $\log k$ phases. In phase $i=0, \dots , \log k - 1$ there are $k/2^i$ sorted arrays, where the arrays of phase $0$ are the $k$ input arrays. These arrays are arbitrarily grouped into $k/2^{i+1}$ pairs and each pair is merged. The resulting arrays are moved to the next phase. At the end of the $(\log k - 1)$-th phase there is only one sorted array $A$ remaining. Return $A$.

The total amount of work on each phase (a level of the tree) is $O(n)$, and the number of phases (i.e., levels) is $O(\log k)$.