2
$\begingroup$

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,

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

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

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