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

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?

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)$$.