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

EP>>Вот на этом этапе алгоритм деления должен быть вполне конкретным — Hoare's partition.
_DA>Кому должен? Вот у Кормена, например, используется Lomuto partition,

Это их фейл.
Даже Степанов этот момент упоминал, конкретно Lomuto vs Hoare partition в CLRS (34:18):
https://youtu.be/d4tFGtGngf4?t=2058
ЕМНИП даже кто-то из CLRS это в своей лекции что-то такое упоминал.

_DA>и что это теперь не Quicksort, а другой алгоритм?

Да, другой алгоритм, с другой сложностью (абсолютной, не асимптотической), с другими скоростными характеристиками.