1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.