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

Question

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,

Answer 1

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