В случае повторяющихся неудачных разбиений опорным элементом, глубина рекурсии может достичь <Tex>O(n)</Tex>. Этого можно избежать, если в цикле разбивать массив, но рекурсивно вызываться только от части, содержащей меньшее число элементов, а большую часть продолжать разбивать в цикле.
==Асимптотика==
===Худшее время работы===
Обозначим худшее время работы за <tex>T(n)</tex>. Получим рекуррентное соотношение
<tex>T(n) = Max(T(q-1)+T(n-q-1))+\Theta(n)</tex>
Предположим, что <tex>T(n) \leq cO(n^2)</tex>. Тогда получим
<tex>T(n) \leq Max(cq^2+c(n-q-1)^2)+\Theta(n) =
cMax(q^2+(n-q-1)^2)+\Theta(n)</tex>
<tex>Max(q^2+(n-q-1)^2) \leq (n-1)^2</tex>
<tex>T(n) \leq cn^2 - c(2n-1) + \Theta(n) \leq cn^2</tex>
Таким образом <tex>T(n) = O(n^2)</tex>
===Среднее время работы===
==Ссылки==
