Concurrent quicksort in C++ I have a task to write a concurrent version of quicksort algorithm, to speed it up. This is what I wrote:

template &lt;class T&gt;
void quicksort::sort(T *data, int len) {
    thread_count = 0;
    int p = 0;
    int r = len - 1;
    _sort(data, p, r);
}

template &lt;class T&gt;
void quicksort::_swap(T *data, int first, int second) {
    auto temp = data[first];
    data[first] = data[second];
    data[second] = temp;
}

template &lt;class T&gt;
void quicksort::_sort(T *data, int p, int r) {
    thread_count++;
    if (p &lt; r) {
        auto q = _partition(data, p, r);
        if (thread_count &gt;= thread_limit) {
            _sort(data, p, q - 1);
            _sort(data, q + 1, r);
        } else {
            std::thread lower(&amp;quicksort::_sort&lt;T&gt;, this, data, p, q - 1);
            std::thread upper(&amp;quicksort::_sort&lt;T&gt;, this, data, q + 1, r);
            lower.join();
            upper.join();
        }
    }
    thread_count--;
}

template &lt;class T&gt;
int quicksort::_partition(T *data, int p, int r) {
    auto first = data[p];
    auto last = data[r];
    T pivot = 0;
    // Median of three
    auto middle = data[(p + 2) / 2];
    if (first &gt; middle) {
        if (middle &gt; last) {
            pivot = middle;
        } else {
            pivot = last;
        }
    } else {
        if (middle &gt; last) {
            pivot = std::max(first, last);
        } else {
            pivot = middle;
        }
    }
    auto i = p - 1;
    for (auto j = p; j &lt; r; ++j) {
        if (data[j] &lt;= pivot) {
            _swap(data, ++i, j);
        }
    }
    _swap(data, i + 1, r);
    return i + 1;
}


Those are methods from class quicksort, which also has std::atomic&lt;int&gt; thread_limit and std::atomic&lt;int&gt; thread_count. 

So f.e I cap the thread limit to f.e maximum 1000 threads. 

The part I am particularly not sure of is the part in _sort() function. Basically, I don't know if my way of starting those threads and then joining them is the right way to do it.

I have a benchmark method, and I benchmarked my quicksort implementation like this: I took the average of 100 benchmarks for every thread_limit from 200 to 2000, stepping by 100 (so 200, 300, 400) and for single-threaded quicksort of mine. And this was for 1.000.000-sized arrays (every time I was creating a new one - this overhead was not measured). The result was shocking for me. It occurred, that of course, even with 2000 threads it was faster than with only 1 thread, but still, the fastest one was with thread_limit = 200. I thought that the optimum would be somewhere nearer the middle.

Sometimes f.e 700 threads were faster than 600 threads, but still, the general rule was: the more threads, the slower.

Do you guys see any flaws in my code or in my understanding of the benchmark I made?
Partition - Pivot selection
There are 2 bugs in the pivot selection code, in combination allowing for \$\mathcal{O}(n^2)\$ worst case runtime.
Bug #1: Wrong average calculation
I guess this is just a typo:
auto middle = data[(p + 2) / 2];

Most likely, (p + r) / 2 was intended instead, and that would fix this problem (disregarding overflow).
Bug #2: Missing a case
if (first &gt; middle) {
    if (middle &gt; last) {
        pivot = middle;
    } else {
        pivot = last;
    }
}

This snippet doesn't handle the case correctly if \$middle &lt; first &lt; last\$. Even though first should be assigned as pivot, last will be.
The fix is simple: Change pivot = last; to pivot = std::min(first, last);.
Consequences
These two bugs allow for runtime complexity to degrade to \$\mathcal{O}(n^2)\$, because they introduce a huge bias towards last as pivot value:
For any call with p &gt;= 4, middle will have the value of an element to the left of data[p], thus being guaranteed to be smaller than first or last due to previous runs of _partition. So `last will be chosen as pivot, due to bug #2.
For any call with p == 2 or p == 3, middle will be assigned the value of data[1], which is equal to first. In that case, pivot will always be assigned the value of middle/first.
For any call with p == 0 or p == 1, the median calculation will work with a slight bias towards last (due to bug #2).
Partition - Moving values
There seems to be an assumption that data[r] == pivot. This might have been a good assumption before due to bug #2, but that isn't necessarily the case once that bug is fixed. There a multiple ways to fix that.
Also, technically it isn't necessary to move values around that are equal to the pivot value: It doesn't actually matter whether they are left or right of the final pivot position.
Multithreading
The current multithreading solution isn't actually that efficient at using threads: Nearly half the threads at a time are waiting for the others to finish. (The first thread is waiting on threads #2 and #3 it spawned, they then are waiting on threads #4-7, ...)
As mentioned in the comments, this could be fixed by letting the original thread keep working on one of the subsections before waiting, i.e. changing this:
        std::thread lower(&amp;quicksort::_sort&lt;T&gt;, this, data, p, q - 1);
        std::thread upper(&amp;quicksort::_sort&lt;T&gt;, this, data, q + 1, r);
        lower.join();
        upper.join();

to:
        std::thread lower(&amp;quicksort::_sort&lt;T&gt;, this, data, p, q - 1);
        _sort(data, q + 1, r);
        lower.join();

Another point to make is that it rarely benefits performance to have a number of threads much larger than the number of available (logical) cores. The final number is likely between #cores and 2 * #cores, but to find the best amount you'll likely need to measure.
Bug #3: No protection for concurrent calls
Since we're already in the multithreaded environment, what happens if a second thread calls quicksort::sort after the first thread, but before that call finished?
It resets thread_count, thus allowing for the creation of more threads than intended. Once they are finished, thread_count will be negative! This might cause problems if that case isn't expected.
Solution: Either don't reset thread_count, or wait until it reaches zero before starting to work on the next dataset.