==Оптимизация глубины рекурсии до O(logn) в худшем случае==
Время работы Во избежание достижения опасной глубины рекурсии в худшем случае (или при приближении к нему) возможна модификация алгоритма сортировки зависит от , устраняющая одну ветвь рекурсии: вместо того, как разбивается массив чтобы после разделения массива вызывать рекурсивно процедуру разделения для обоих найденных подмассивов, рекурсивный вызов делается только для меньшего подмассива, а больший обрабатывается в цикле в пределах этого же вызова процедуры. С точки зрения эффективности в среднем случае разницы практически нет: накладные расходы на каждом шагедополнительный рекурсивный вызов и на организацию сравнения длин подмассивов и цикла — примерно одного порядка. В случае повторяющихся неудачных разбиений опорным элементом, Зато глубина рекурсии может достичь ни при каких обстоятельствах не превысит log<Texsub>O(n)2</Tex> а время работы алгоритма <texsub>O(n^2)</tex>. Этого можно избежать, если а в цикле разбивать массив, но рекурсивно вызываться только от части, содержащей меньшее число элементов, а большую часть продолжать разбивать худшем случае вырожденного разделения она вообще будет не более 2 — вся обработка пройдёт в циклепервого уровня рекурсии.
== Ссылки ==
