PHP 7 Data Structures and Algorithms

Complexity of merge sort

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:

Best time complexity ...