Time Complexity of MergeSort Algorithm

 In estimating the running time of an algorithm using the Big O notation, we are only concerned with how the time varies with increasing inputs. So, we forget any run time that doesn't depend on the input. In essence, we forget any constant. We approximate, take upper bounds and use worst case scenarios.
 With the above principles in mind, to estimate the running time of the mergesort algorithm, we don't need to get into the internals; simply view it at a high level of abstraction. Let's rewrite the MergeSort function:
 MergeSort(A, p, r)
If (p < r) {
  1. q = (p+r)/2
  2. Mergesort (A, p, q)
  3. MergeSort (A, q+1, r)
  4. Merge (A, p, q, r)
}
Line 1 is a primitive operation with constant time so it doesn't count in our total running time. So, we continue to forget line 1.
Line 2 and 3 are simply nothing more than the MergeSort function again. So, at this point we should notice that Line 1 and 4 are the only components of a MergeSort function. Because with that in mind, it is easy to see that the whole MergeSort function applied on the array A to be sorted is nothing but collection of nested MergeSort functions(one inside another) which in turn is nothing but simply, a collection of nested Merge functions(each inside the respective  MergeSort function). Hence, everything happens inside the merge function and as such, we use only it in our run time computation.
 Now, looking into the Merge Function, we see that we have summation of running times like the time to copy the correct elements from the array A to form the L and H subarray and the time taken to make comparisons and make the necessary sorting in the array A. For the later, we see that at maximum which is when we are merging two halves of the original array, the number of comparisons to make is n, the number of elements in the array A. Usually, we don't include the time taken to copy elements into the subarrays because even if you include it alongside all other running times, you will find out that you get something like say 0.5n + n + n.... which can all be summed to give some constant times n, Cn. Since in big o, we care only about the order, then we forget the constant and so, it is simply n. So far, we have n. Next is to realise that all these is for one Merge Function. Therefore the total running time would be
 n × number of Merge functions----(1)
 Each Merge function signifies a step where two arrays are merged. Now try visually sketching and experimenting with arrays of different sizes breaking them up and merging according to the MergeSort algorithm you will find out that you need two mergings or steps  when sorting  a given array of size 4 using the merge sorting algorithm and three mergings or step when sorting an array of size 6 .....and so on. You will realise that the number of mergings is roughly, approximately equal to log to base 2 of the size of the original array i.e. logn.
  So, substituting in 1 above, we have:
Total runtime= O(nlgn)
 i.e.
= O(n×logn)
 where log here is log to base 2.