Вот есть такая реализация быстрой сортировки:
template<class iterator>
void qsort(iterator begin, iterator end)
{
if (begin == end)
return;
const auto distance = std::distance(begin, end);
iterator p = std::next(begin, distance / 2);
iterator it1 = std::partition(begin, end, [&p](const auto& v){ return v < *p;});
iterator it2 = std::partition(it1, end, [&p](const auto& v) { return !(v > *p);});
qsort(begin, it1);
qsort(it2, end);
}
Я хочу реализовать паралельное выполнение этого алгоритма. Можно конечно сделать так:
template<class iterator>
void qsort(iterator begin, iterator end)
{
if (begin == end)
return;
const auto distance = std::distance(begin, end);
iterator p = std::next(begin, distance / 2);
iterator it1 = std::partition(begin, end, [&p](const auto& v){ return v < *p;});
iterator it2 = std::partition(it1, end, [&p](const auto& v) { return !(v > *p);});
std::thread t1(qSort<Iterator>, begin, middle1);
std::thread t2(qSort<Iterator>, middle2, end);
t1.join();
t2.join();
}
но это очевидно далеко не лучшая реализация т.к. количество потоков будет равно log(n)
.
Вопрос: как правильно реализовать многопоточный алгоритм быстрой сортировки? Можно написать класс который будет лимитировать количество потоков и передавать его в функцию, но стандартная реализация std::sort
может выполняться в нескольких потоков, при этом ее сигнатура не меняется, хотелось бы реализовать что-то подобное.