Partial insertion sort

o que difere este algoritmo do original é que ele

1. Realiza um insertion sort normal para os k primeiros elementos ())
2. Para cada elemento fora desse intervalo, ele compara o valor destes com o do ultimo ( e maior ) elemento contudo no intervalo e, se for o caso, troca esses elementos de lugar, chamando novamente insertion sort nos k primeiros elementos para ordená-los ()

A complexidade desse algoritmo fica então:

$$\begin{eqnarray*} T(n) & = & O(nk^{2}+k^{2}-k^{3})\\ & & \end{eqnarray*}$$

Logo, esse algoritmo, com L pequenos é bom, pois o fator fica minimizado. Mas, aumentos em acarreta um crescimento muito grande na parcela