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


MTD>>>Выбор опорной точки не поможет.

Q>>Как это не поможет?

MTD>Да вот так. На отсортированных данных как опорные точки не ставь скорость алгоритма деградирует до квадратичной.

Почему это ?? Тривиальный выбор опорной точки (arr[l + (r — l) / 2]) на отсортированной последовательности делит массисы всегда пополам, никакого квадрата не будет. Худший случай — это массив типа: 1,2,...,X-1,X,X-1,...,2,1.
MS в этом месте споткнулась (правда в .NET'е) https://github.com/dotnet/corefx/issues/24110

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


MTD>>>Выбор опорной точки не поможет.

Q>>Как это не поможет?

MTD>Да вот так. На отсортированных данных как опорные точки не ставь скорость алгоритма деградирует до квадратичной.

Почему это ?? Тривиальный выбор опорной точки (arr[l + (r — l) / 2]) на отсортированной последовательности делит массивы всегда пополам, никакого квадрата не будет. Худший случай — это массив типа: 1,2,...,X-1,X,X-1,...,2,1.
MS в этом месте споткнулась (правда в .NET'е) https://github.com/dotnet/corefx/issues/24110