The worst case running time for an array of length $n$ satisfies the following recurrence relation: $T(n)=\begin{cases} \Theta(1) &n=1 \\ T\left( \lfloor \frac{n}{2} \right \rfloor) + T\left(n- \lfloor \frac{n}{2} \right \rfloor ) + \Theta(n) & \text{otherwise} \end{cases}$ If $n$ is even then $T(n) =2T\left( \frac{n}{2} \right)+\Theta(n)$. **Proposition**. $T(n)=T\left( \frac{n}{2} \right)+\Theta(n)$ has a time complexity of $\mathcal{O}(n\log n)$ if $n>1$. *Proof*. For $n=2$, $T(2)\leq 2c\log_{2}(2) = 2c$ for some constant $c$. Assume $T(k)\leq ck\log(k)$ for all $k\leq n$, then $\begin{align} T(n) &= 2T\left( \frac{n}{2} \right) + \Theta(n) \leq 2c\left( \frac{n}{2} \right) \log\left( \frac{n}{2} \right) +cn \\ &=2cn\log n. \end{align}$ Follows also from [[Master Theorem for Polynomial Work]].