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,