Здравствуйте, Jack128, Вы писали:

J>Почему это ?? Тривиальный выбор опорной точки (arr[l + (r — l) / 2]) на отсортированной последовательности делит массивы всегда пополам, никакого квадрата не будет. Худший случай — это массив типа: 1,2,...,X-1,X,X-1,...,2,1.

Тут ты прав, я выразился не точно. Если брать крайний опорный элемент — деградируем на упорядоченных, если брать средний — на упорядоченных горкой, если брать рандом — ну как повезет. В любом случае алгоритм чувствителен к входным данным.