Merge sort on n elements:
- If n = 1 , return the solitary element.
- Else , Recursively sort [1...n/2] elements and [n/2+1...n] elements.
- Merge the 2 sorted arrays.
Let the total time taken to merge-sort an array of n elements be T(n). As we know the base case is if the number of elements n is 1 , then we don't need to apply merge sort algorithm , we can just return that element .
if n=<1 then return L
This will take a constant time , say c1.
If elements are greater than 1 then split the array from [1..n/2] and [n/2+1...n] and recursively merge-sort them.
L1 <- MergeSort(L1... n/2)
L2 <- MergeSort(L(n/2 +1) ... n)
So, as we assumed the time taken to merge-sort n elements is T(n) , then the time taken to sort each of the sub-array containing approximately n/2 elements will be T(n/2).
We need to merge the sub-arrays after sorting , time taken to merge n elements will be linear function of the n i.e. c2.n where c2 is the constant time taken to place an element in its specific position in the final sorted array.