Merge sort is a devide and comquer algorithm, as outlined below.
list mergesort (list L,int n)
split L in to two halves L-1 and L-2.
return Merge( mergesort(L-1 ,n/2),mergesort(L-2,n/2) )
Let T(n) be the running time of merge sort on an input list of size n.
T(n) ≤ C1 if( n=1 ) ( C1 is a constant )
≤ 2×T(n/2) + C2×n if(n > 1)
(for two recursive calls) (cost of merging)
if n= 2^k for some k , it can be shown that
T(n) ≤ (2^k) ×T(1) + C2 × k× (2^k)
That is , T(n) is order of O(nlog(n) ).