Sort2

Esse algoritmo é muito parecido com o anterior.

A sua fórmula de recorrência é:

$$T\left( n\right) =\left\{ \begin{array}{c} 1,\\ 3T\left( \frac{n}{3}\right) +\frac{5n}{3}-2 \end{array}para\right. n=1$$

Aplicando o Master Theorem[1, p62], tendo que , e , chegamos ao resultado que

$$f\left( n\right) =\Theta \left( n^{\log _{b}a}\right) \Right... ...eft( n^{\log _{3}3}\log n\right) =\Theta \left( n\log n\right)$$