BEST CASE TIME COMPLEXITY

The best case time complexity for Merge sort would be the given array or linked list to be sorted is already in ascending order i.e it is already sorted.

Consider the given array :

In merge sort the given array is divided and then it is sorted during merging. Merge sort using Divide and Conquer Approach.So here we divide the given array in two equal halves and keep it dividing by half until it cant be divided further.
So,here the dividing factor for merge sort is n/2.
The recurrence relation would be :
T(n) = 2*T( $\raisebox{1ex}{$\frac{n}{2}$}\!\left/ \!\raisebox{-1ex}{$$}\right.$) + n ..............(1)
Here the dividing factor is n/2 so substitute the value of n as n/2.
T( $\raisebox{1ex}{$\frac{n}{2}$}\!\left/ \!\raisebox{-1ex}{$$}\right.$) = 2*T( $\raisebox{1ex}{$\frac{n}{4}$}\!\left/ \!\raisebox{-1ex}{$$}\right.$) + $\raisebox{1ex}{$\frac{n}{2}$}\!\left/ \!\raisebox{-1ex}{$$}\right.$ ..............(2)
T( $\raisebox{1ex}{$\frac{n}{4}$}\!\left/ \!\raisebox{-1ex}{$$}\right.$) = 2*T( $\raisebox{1ex}{$\frac{n}{8}$}\!\left/ \!\raisebox{-1ex}{$$}\right.$) + $\raisebox{1ex}{$\frac{n}{4}$}\!\left/ \!\raisebox{-1ex}{$$}\right.$ ..............(3)


Now we have to perform backsubstitution to get the value of T(n).
T(n) = 2*T( $\raisebox{1ex}{$\frac{n}{4}$}\!\left/ \!\raisebox{-1ex}{$$}\right.$) + n .............from eq(1)
T(n) = 2*[2*T( $\raisebox{1ex}{$\frac{n}{4}$}\!\left/ \!\raisebox{-1ex}{$$}\right.$)+ $\raisebox{1ex}{$\frac{n}{2}$}\!\left/ \!\raisebox{-1ex}{$$}\right.$] + n
T(n) = 4*T( $\raisebox{1ex}{$\frac{n}{4}$}\!\left/ \!\raisebox{-1ex}{$$}\right.$) + 2n ..............(4)
T(n) = 4*[2*T( $\raisebox{1ex}{$\frac{n}{8}$}\!\left/ \!\raisebox{-1ex}{$$}\right.$)+ $\raisebox{1ex}{$\frac{n}{4}$}\!\left/ \!\raisebox{-1ex}{$$}\right.$] + n
T(n) = 8*T( $\raisebox{1ex}{$\frac{n}{8}$}\!\left/ \!\raisebox{-1ex}{$$}\right.$) + 3n ..............(5)

from above eq(4),(5) we can conclude that :
T(n) = 2^k * T($\raisebox{1ex}{$\frac{n^{}}{2^{\mathrm{k}}}$}\!\left/ \!\raisebox{-1ex}{$$}\right.$) + kn .............(A)

Here we consider n/2^k as 1 so that we can efficiently find the time complexities.
n/2^k = 1
n = 2^k
taking log on both sides.
log n = log(2^k)
i.e. logn =klog₂2
logn = k
eq.(A) becomes :
T(n) = n*T(1) + nlogn
i.e. T(n) = n + nlogn
T(n) = nlogn ............considering only dominant terms

WORST CASE TIME COMPLEXITY

The best case time complexity for Merge sort would be the given array or linked list is sorted in descending order .

Consider the given array :

The merge sort performs same irrespective of the input provided.Hence the time complexity for merge sort is O(nlogn) for worst case time complexity as well.

AVERAGE CASE TIME COMPLEXITY

The average case time complexity for Merge sort would be the given array or linked list is in random order.
Consider the given array :

The merge sort performs same irrespective of the input provided.Hence the time complexity for merge sort is O(nlogn) for average case time complexity as well.