Есть ли недостатки у такой реализации быстрой сортировки, если не иметь в виду очевидные алгоритмические улучшения типа хорошего выбора опорного элемента и избавления от одного рекурсивного вызова?
Меня смущает сжатость процедуры разбиения. В интернете встречаются реализации классического партишена в 2 - 2.5 раза длиннее моей, поэтому мне кажется, что я что-то упустил.
template<class Iter>
Iter partition(Iter first, Iter last)
{
Iter pivot = last - 1;
Iter right = first;
for (auto unknown = first; unknown != last - 1; ++unknown)
{
if (*unknown <= *pivot)
{
std::iter_swap(right, unknown);
++right;
}
}
std::iter_swap(right, pivot);
return right;
}
template<class Iter>
void quick_sort(Iter first, Iter last)
{
if (std::distance(first, last) > 1)
{
auto q = partition(first, last);
quick_sort(first, q);
quick_sort(q + 1, last);
}
}