Let $A(x) = \sum_{j=0}^n a_jx^j$ and $B(x) = \sum_{j=0}^n b_jx^j$, and set $C(x) := A(x)B(x)$. The naive way to compute the product $A(x)B(x)$ is by convolution: $C(x) = \sum_{j=0}^{2n} c_jx^j$ where
$$
c_j = \sum_{k=0}^j a_kb_{j-k},\quad 0\leqslant j\leqslant 2n.
$$
This takes $\Theta(n^2)$ time, since we perform $j+1$ multiplications and $2n+1$ additions to compute each $c_j$, and hence $\sum_{j=0}^{2n} (j+1) = (1+n)(1+2n) =$ multiplications and $n(2n+1)$ additions.
The divide and conquer approach is to split $A$ and $B$ each into polynomials of degree $\sim\frac n2$, i.e.
$$
A_0(x) = \sum_{j=0}^{\left\lfloor\frac n2\right\rfloor-1}a_jx^j,\quad A_1(x) = \sum_{j=\left\lfloor\frac n2\right\rfloor}^{n}a_jx^{j-\left\lfloor\frac n2\right\rfloor}.
$$
Then $A(x) = A_0(x) + A_1(x)x^{\left\lfloor\frac n2\right\rfloor}$. Define $B_0(x)$ and $B_1(x)$ similarly, then
\begin{align}
A(x)B(x) &= \left(A_0(x) + A_1(x)x^{\left\lfloor\frac n2\right\rfloor}\right)\left(B_0(x) + B_1(x)x^{\left\lfloor\frac n2\right\rfloor}\right)\\
&=A_0(x)B_0(x) + A_0(x) B_1(x)x^{\left\lfloor\frac n2\right\rfloor} + A_1(x)B_0(x) + A_1(x)B_1(x)x^{2\left\lfloor\frac n2\right\rfloor}.
\end{align}
This divides a problem of size $n$ into $4$ problems of size $\left\lfloor\frac n2\right\rfloor$, each of which take $\Theta(n)$ time. This yields the recurrence $T(n) = 4T(\left\lfloor\frac n2\right\rfloor) + Cn$, where $C$ is constant. Assuming $T(1)\in\Theta(1)$ and $n=2^m$, we have
\begin{align}
T(n) &= T\left(2^m\right)\\
&= 4^m + \sum_{j=0}^{m-1}2^jCn\\
&= 4^m + Cn(2^m-1)\\
&= n^2 +Cn(n-1),
\end{align}
so that $T(n)\in\Theta(n^2)$ - no improvement!
The trick is that it actually only takes three multiplications in each subproblem. To find $A_0B_0$, $A_0B_1$, $A_1B_0$, and $A_1B_1$, we need only to compute
$$
A_0B_0,\quad A_0B_1 + A_1B_0,\quad A_1B_1,
$$
since $$A_0B_1 + A_1B_0 = (A_0 + A_1)(B_0 + B_1) - A_0B_0 - A_1B_1.
$$
Then we have the recurrence $T(n) = 3T(\left\lfloor\frac n2\right\rfloor) + Cn$, so that
\begin{align}
T(n) &= T(2^m)\\
&= 3^m + \sum_{j=0}^{m-1}\left(\frac32\right)^jCn\\
&= 3^m + Cn\left(\left(\frac32\right)^m-1\right)\\
&= 3^{\lg n} + Cn\left(\left(\frac32\right)^{\lg n}-1\right)\\
&= n^{\lg 3} + Cn\left(n^{\lg 3 -1}-1\right)\\
&= n^{\lg 3}(1 + C) - Cn,
\end{align}
and hence $T(n)\in\Theta\left(n^{\lg 3}\right)$.
Best Answer
As the title suggests you will need to apply a divide and conquer idea. So the difficult part is the merge part. Let the following pseudo-code
Since the merge is done in $\mathcal O(n)$ so the complexity is $\mathcal O(n\log(n))$.