T(n) = 2T(n/2) + n ..........(1)
T(n/2) = 2T(n/4) + n/2 ........(2)
Put (2) in (1)
$\therefore$ T(n) = 2 { 2T(n/4) + n/2 } + n
= 22T(n/4) + n + n
= 23T(n/8) + n + n + n
= 24T(n/16) + n + n + n + n
= 2kT(n/2k) + n + n + n + n + n.....(k times n will be present)
= 2kT(n/2k) + nk
Now put 2k = n, so k will be log2n
So, T(n) = nT(2k/2k) + nlog2n
= nT(1) + nlog2n
= n + nlog2n
Hence, T(n) = O( nlog2n )