SORTING BY MERGING

• Mergesort
  
  • $W(n)=O(n)+2w(n/2)$
    $=n+2w(n/2)$
    $=n+2(n/2+2w(n/2^{2})$
    $=n+n+2^{2}w(n/2^{2})$
    $=2n+2^{2}w(n/2^{2})$
    $=2n+2^{2}(n/2^{2}+2w(n/2^{3}))$
    $=3n+2^{3}w(n/2^{3})$
    $\cdots$
    $=kn+2^{k}w(n/2^{k})$
    $w(n/2^{k})=w(1)=0$
    $n/2^{k}=1$, $k= \log_{2} n$
    $\Rightarrow W(n)=\theta(n \log n)$
    
  • Recursion tree for $W(n)$
  • $S(n)=O(n)$
    Can be reduced to $O(1)$ but algorithm slows down.
    A temporary array of half the size is required, however.