# Running time analysis for algorithm that merges $k$ sorted arrays to one sorted array

Given $$k$$ sorted arrays, the size of each array is $$n$$ and we want to sort them to one sorted array. assume that $$k=2^p$$ i.e $$k\in\{ 2^1,2^2,2^3,2^4,\dots\}$$

I the first step we will merge (the first and the second arrays),(the third and the fourth arrays),(the fifth and the sixth arrays),... till we get sorted arrays with length of $$2n$$

In the second step we will merge again each successive pair till we get sorted arrays with length of $$4n$$

I need to find the time complexity of this algorithem.

What I tried:

I know that merging two sorted arrays one with length $$t$$ and the other with length $$r$$ takes $$\Theta (t+r)$$ .

In this case the length of each array in the first iteration is $$n$$, so:

• In the first iteration: merging each pair takes $$\Theta(n+n)$$ and there are $$k/2$$ merges so $$\Longrightarrow \frac k 2 \Theta(2n)$$

• In the second iteration: merging each pair takes $$\Theta(2n+2n)$$ and there are $$k/2^2$$ merges so $$\Longrightarrow \frac k 4 \Theta(4n)$$

• In the third iteration: merging each pair takes $$\Theta(4n+4n)$$ and there are $$k/2^3$$ merges so $$\Longrightarrow \frac k 8 \Theta(8n)$$

• In the i-th iteration: merging each pair takes $$\Theta(2^in)$$ and there are $$k/2^i$$ merges so $$\Longrightarrow \frac k {2^i} \Theta(2^in)$$

I got stuck here, I know that binary search takes $$\Theta (\log n)$$ because it divides the array to two in each iteration and here it should be ralated to $$\log$$ somehow,

• Write out the algorithm in pseudocode first; that can guide your thoughts. Then, proceed systematically. Don't $\Theta$-round until the very end.
– Raphael
Apr 9, 2016 at 16:39
• What has binary search to do with anything?
– Raphael
Apr 9, 2016 at 16:39

You are almost there. In the first merge pass we do $\frac{k}{2}$ merges each taking time proportional to $2n$. In the second merge pass $\frac{k}{4}$ merges each taking $4n$ (note how nicely the factors 2 and 4 cancel and each merge pass runs in $\Theta(nk)$ time). Finally, since we need only $p = \log_2k$ merge passes, we obtain the running time of $\Theta(nk \log k)$.