Since merge sort follows the divide-and-conquer method, we have to address both complexities here. For an n-sized array, we first need to divide the array into two halves and then merge them to get an n-sized array. This can be written in terms of T(n) as:

T(n)     = T(n/2) + T(n/2) + n    , for N>1 with T(1) = 0 
         = 2 T(n/2)+n 

T(n)/n   = 2 T(n/2)/n + 1              // divide both side by n 
         = T(n/2)/(n/2)  + 1                  
         = T(n/4)/(n/4)  + 1+ 1        // telescoping 
         = T(n/8)/(n/8)  + 1+ 1 + 1      // again telescoping 
         = ...... 
         = T(n/n)/(n/n)  + 1 + 1 + 1 + ....... + 1 
         = log (n)                     // since T(1) = 0      

So T(n)  = n log (n)                   // multiply both side with n 

So, the complexity for merge sort is O(n log(n)). Here is the complexity chart for merge sort: