Using inductive hypothesis on recurrence relation?
We can open up the recursion to obtain
\begin{align}
T(n) &amp;\leq n \log n + 2\lfloor n/2\rfloor \log \lfloor n/2 \rfloor + 4\lfloor \lfloor n/2 \rfloor/2\rfloor \log \lfloor \lfloor n/2 \rfloor/2\rfloor \\ &amp;\leq
n\log n + n \log (n/2) + n\log (n/4) + \cdots \\ &amp;\leq
n\log n + n\log n + \cdots \\ &amp;= O(n\log^2 n),
\end{align}
since it takes $\Theta(\log n)$ steps to get to the base case.
If you're more careful, you can show that in fact $T(n) = \Theta(n\log^2 n)$.