4 a. The outer loop that decides the size of the window increments by a factor of 2.
So at \(i^{th}\) Iteration when the window size reaches the size of the given array,
\(\Rightarrow\ 2^i=n\) (Assuming the size of the array is a power of 2)
\(\Rightarrow i\ =\ \log_2n\)
So time taken to merge two sub arrays that are sorted takes \(\frac{n}{2}+\frac{n}{2}=n\ time\)
So we merge total of \(i\ \) times, the maximum time taken by the algorithm would become,
\(\Rightarrow O\left(n\log_2n\right)\)
b. Advantage: The recursive implementation involves calling the stack for bookkeeping purposes which creates a lot of overhead.
Disadvantage: