Recursion solves a problem through calls that handle smaller instances. In Quicksort, partitioning first identifies which elements belong before or after a pivot; each side is then sorted recursively. Because the divisions emerge during processing, they cannot be assigned to threads up front. section 8.1.2 section 8.1.1
After partitioning, the recursive calls sort separate sets of elements, so they can run concurrently. Using std::async for one recursive branch lets the C++ Thread Library choose whether to run it on a new thread or synchronously. Creating a thread at every level can cause excessive thread counts or exhaust available threads. section 8.1.2
To limit thread creation, the recursive workload can be managed in other ways:
- Choose a thread count with std::thread::hardware_concurrency() and place chunks awaiting sorting on a thread-safe stack. section 8.1.2
- For accumulate, recursively divide the reduction when there are more threads than the minimum number of items per thread, or let workers perform reduction steps as they finish. section 8.1.1
A diagram of recursive data division in Quicksort. section 8.1.2
