aka Two figures algorithm.
Merge sort is a recursive algorithm. It works as follows.
- Divides the array into two part and then merge them back.
- Each half will again perform #1 (until there are only two elements remaining)
We have 1+log n levels and n leaves. For each level its Cn of work.
So T(n) = (1+logn)*Cn = Θ (n Log n)
Merge sort needs Θ (n) auxiliary space.
We also have In-place Merge Sort which will not take more space but time complexity is very high.