The solution of the recurrence T(n) = 2T(n/2) + n log n is

Explanation

Here f(n) = n log n = Θ(n^(log₂2) · log n), the extended case 2 of the Master theorem with k = 1, giving Θ(n log^(k+1) n) = Θ(n log² n).